A set of families of analytically described triple loop networks defined by a parameter

E. A. Monakhova

Prikladnaâ diskretnaâ matematika, no. 3 (2020), pp. 108-119.

Résumé

A set of families of undirected triple loop networks of the form $C(N(d,p); 1, s_2(d,p),$ $ s_3(d,p))$ with the given diameter $d>1$ and a parameter $p=1, 2, \ldots, d-1$ is obtained. For each such family, the order $N$ of every graph in the family and its generators $s_2$ and $s_3$ are defined by a cubical polynomial function of the diameter. The found set includes circulant graphs of degree 6 with the largest known orders for any diameters $d\equiv 0 \pmod 3$ and $d\equiv 2 \pmod 3$. Examples of constructing new families of triple loop networks based on the definition of functions $p=p(d)$ are presented.

Détail

Keywords: undirected triple loop networks, circulant graphs of degree $6$ with given diameter, families of circulant graphs.

Bibliographie

[1] Monakhova E. A., “Structural and communicative properties of circulant networks”, Prikladnaya Diskretnaya Matematika, 2011, no. 3, 92–115 (in Russian)

[2] Monakhova E. A., “A survey on undirected circulant graphs”, Discrete Math. Algorithms Appl., 2012, no. 4 https://www.researchgate.net/publication/267143246_A_survey_on_undirected_circulant_graphs | MR | Zbl

[3] Perez-Roses H., “Algebraic and computer-based methods in the undirected degree/diameter problem — A brief survey”, Electr. J. Graph Theory Appl., 2:2 (2014), 166–190 | DOI | MR | Zbl

[4] Bermond J.-C., Comellas F., Hsu D. F., “Distributed loop computer networks: a survey”, J. Parallel Distributed Comput., 24 (1995), 2–10 | DOI

[5] Hwang F. K., “A survey on multi-loop networks”, Theor. Comput. Sci., 299 (2003), 107–121 | DOI | MR | Zbl

[6] Romanov A., Amerikanov A., Lezhnev E., “Analysis of approaches for synthesis of networks-on-chip by using circulant topologies”, J. Physics: Conf. Ser., 1050 (2018), 1–12 | DOI

[7] Romanov A. Yu., “Development of routing algorithms in networks-on-chip based on ring circulant topologies”, Heliyon, 5:4 (2019), 1–23 | DOI

[8] Romanov A. Yu., Vedmid E. A., Monakhova E. A., “Designing networks-on-chip based on triple loop (circulant) networks: routing algorithm development”, Informacionnye Tekhnologii, 25:9 (2019), 522–530 (in Russian) | MR

[9] Yebra J. L. A., Fiol M. A., Morillo P., Alegre I., “The diameter of undirected graphs associated to plane tessellations”, Ars Combinatoria, 20B (1985), 159–172 | MR

[10] Wong C. K., Coppersmith D., “A combinatorial problem related to multimodule memory organizations”, J. Assoc. Comput. Mach., 21 (1974), 392–402 | DOI | MR | Zbl

[11] Chen S., Jia X.-D., “Undirected loop networks”, Networks, 23 (1993), 257–260 | DOI | MR | Zbl

[12] Barriere L., Fabrega J., Simo E., Zaragoza M., “Fault-tolerant routings in chordal ring networks”, Networks, 36:3 (2000), 180–190 | 3.0.CO;2-R class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[13] Thomson A., Zhou S., “Gossiping and routing in undirected triple-loop networks”, Networks, 55:4 (2010), 341–349 | DOI | MR | Zbl

[14] Liestman A. L., Opatrny J., Zaragoza M., “Network properties of double and triple fixed-step graphs”, Int. J. Found. Comp. Sci., 9 (1998), 57–76 | DOI | Zbl

[15] Jha P. K., “A family of efficient six-regular circulants representable as a Kronecker product”, Discr. Appl. Math., 203 (2016), 72–84 | DOI | MR | Zbl

[16] Monakhova E., “Optimal triple loop networks with given transmission delay: Topological design and routing”, Intern. Network Optimization Conf., INOC'2003 (Evry/Paris, France, 2003), 410–415

[17] Monakhova E. A., Monakhov O. G., “A dynamic algorithm of two-terminal routing for analytically described families of degree six circulant networks”, Proc. XIX Intern. Conf. “Problemy Informatiki v Obrazovanii, Upravlenii, Ekonomike i Tekhnike”, PDZ Publ., Penza, 2019, 30–37 (in Russian)