Series of families of degree six circulant graphs

E. A. Monakhova

Prikladnaâ diskretnaâ matematika, no. 4 (2021), pp. 109-124.

Résumé

An approach for constructing and optimizing graphs of series of analytically described circulant graphs of degree six with general topological properties is proposed. The paper presents three series of families of undirected circulants having the form $C(N(d,p); 1, s_2(d,p), s_3(d,p))$, with an arbitrary diameter $d>1$ and a variable parameter $p(d)$, $1\le p(d)\le d$. The orders $N$ of each graph in the families are determined by a cubic polynomial function of the diameter, and generators $s_2$ and $s_3$ are defined by polynomials of the diameter of various orders. We have proved that the found series of families include degree six extremal circulant graphs with the largest known orders for all diameters. By specifying the functions $p(d)$, new infinite families of circulant graphs including solutions close to extremal graphs are obtained.

Détail

Keywords: Abelian Cayley graph, degree/diameter problem, families of degree six circulant graphs, triple loop graphs, extremal circulant graphs.

Bibliographie

[1] Monakhova E. A., “A survey on undirected circulant graphs”, Discr. Math. Algorithms Appl., 4:1 (2012), 1250002, 30 pp. | DOI | MR | Zbl

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

[3] Feria-Puron R., Pérez-Rosés H., Ryan J., “Searching for Large Circulant Graphs”, Aug. 11, 2018, 31 pp., arXiv: 1503.07357v1 [math.CO]

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

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

[6] Stojmenović I., “Multiplicative circulant networks. Topological properties and communication algorithms”, Discr. Appl. Math., 77 (1997), 281–305 | DOI | MR | Zbl

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

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

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

[10] Lewis R. R., “The degree-diameter problem for circulant graphs of degree 8 and 9”, Electron. J. Combin., 21:4 (2014), P4.50 | DOI | MR | Zbl

[11] Lewis R. R., “The degree-diameter problem for circulant graphs of degrees 10 and 11”, Discrete Math., 341 (2018), 2553–2566 | DOI | MR | Zbl

[12] Dalfó C., Fiol M. A., Lopéz N., Ryan J., “An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs”, Discr. Math., 343:10 (2020) | MR | Zbl

[13] Miller M., Siran J., “Moore graphs and beyond: A survey of the degree/diameter problem”, Electron. J. Combin., Dyn. Surv., 2005, DS14, 61 pp. | MR | Zbl

[14] Pérez-Rosés H., “Algebraic and computer-based methods in the undirected degree/diameter problem – A brief survey”, Electron. J. Graph Theory Appl., 2:2 (2014), 166–190 | DOI | MR

[15] The Degree/Diameter Problem For Circulant Graphs, http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Circulant_Graphs

[16] Monakhova E. A., Romanov A. Yu., Lezhnev E. V., “Shortest path search algorithm in optimal two-dimensional circulant networks: Implementation for networks-on-chip”, IEEE Access, 2020, no. 8, 215010–215019 | DOI | MR

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

[18] Monakhova E. A., Monakhov O. G., Romanov A. Yu., Lezhnev E. V., “Analytical routing algorithm for networks-on-chip with the three-dimensional circulant topology”, Proc. MWENT 2020 (Moscow, Russia, March 11–13, 2020), 1–6

[19] Romanov A. Yu., Starykh V. A., “Routing in triple loop circulants: A case of networks-on-chip”, Heliyon, 6:7 (2020), 1–7 | DOI

[20] Ansari A. Q., Ansari M. R., Khan M. A., “Modified quadrant-based routing alglrithm for 3D torus network-on-chip architecture”, Perspect. Sci., 8 (2016), 718–721 | DOI

[21] Joseph J. M., Blochwitz C., Garcia-Ortiz A., Pionteck T., “Area and power savings via asymmetric organization of buffers in 3D-NoCs for heterogeneous 3D-SoCs”, Microprocess. Microsyst., 48 (2017), 36–47 | DOI

[22] 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–171 | MR | Zbl

[23] Martinez C., Stafford E., Beivide R., Gabidulin E. M., “Modeling hexagonal constellations with Eisenstein — Jacobi graphs”, Problems Inform. Transmission, 44:1 (2008) | DOI | MR

[24] Barrière L., Fàbrega J., Simo E., Zaragozá 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

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

[26] 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

[27] Parhami B., “A class of odd-radix chordal ring networks”, CS'J J. Comput. Sci. Eng., 4:2–4 (2006), 1–9

[28] Dougherty R. and Faber V., “The degree-diameter problem for several varieties of Cayley Graphs, 1: The Abelian case”, SIAM J. Discr. Math., 17:3 (2004), 478–519 | DOI | MR | Zbl

[29] Monakhova E. A., “A set of families of analytically described triple loop networks defined by a parameter”, Prikladnaya Diskretnaya Matematika, 2020, no. 49, 108–119 (in Russian) | DOI | MR | Zbl

[30] Monakhova E. A., Monakhov O. G., “A dynamic algorithm of two-terminal routing for analytically described families of circulant networks of degree six”, Proc. XIX Inter. Conf. “Problems of Information in Education, Management, Economics and Technology” (Penza, Russia, 2019), 30–37 (in Russian)