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, s2(d,p), s3 (d,p)), with an arbitrary diameter d > 1 and a variable parameter p(d), 1 ≤ p(d) ≤ d. The orders N of each graph in the families are determined by a cubic polynomial function of the diameter, and generators s2 and s3 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.
Download file
Counter downloads: 314
- Title Series of families of degree six circulant graphs
- Headline Series of families of degree six circulant graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 54
- Date:
- DOI 10.17223/20710410/54/6
Keywords
Abelian Cayley graph, degree/diameter problem, families of degree six circulant graphs, triple loop graphs, extremal circulant graphsAuthors
References
Monakhova E. A. A survey on undirected circulant graphs. Discr. Math. Algorithms Appl., 2012, vol.4, no. 1, 1250002, 30 p.
Bermond J.-C., Cornelias F., and Hsu D.F. Distributed loop computer networks: a survey. J. Parallel Distrib. Comput., 1995, vol. 24, pp. 2-10.
Feria-Puron R., Perez-Roses H., and Ryan J. Searching for Large Circulant Graphs. arXiv:1503.07357v1 [math.CO], Aug. 11, 2018, 31 p.
Hwang F. K. A survey on multi-loop networks. Theor. Comput. Sci., 2003, vol. 299, pp.107-121.
Chen S. and Jia X.-D. Undirected loop networks. Networks, 1993, no. 23(4), pp. 257-260.
Stojmenovie I. Multiplicative circulant networks. Topological properties and communication algorithms. Discr. Appl. Math., 1997, no. 77, pp. 281-305.
Thomson A. and Zhou S. Gossiping and routing in undirected triple-loop networks. Networks, 2010, no. 55(4), pp. 341-349.
Wong C. K. and Coppersmith D. A combinatorial problem related to multimodule memory organizations. J. Assoc. Comput. Mach., 1974, no. 21(3), pp. 392-402.
Monakhova E. Optimal triple loop networks with given transmission delay: Topological design and routing. Proc. INOC’2003, Evry/Paris, France, 2003, pp. 410-415.
Lewis R. R. The degree-diameter problem for circulant graphs of degree 8 and 9. Electron. J. Combin., 2014, no. 21(4), article no. P4.50.
Lewis R. R. The degree-diameter problem for circulant graphs of degrees 10 and 11. Discrete Math., 2018, no. 341, pp. 2553-2566.
Dalfo C., Fiol M. A., Lopez N., and Ryan J. An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs. Discr. Math., 2020, vol. 343, no. 10.
Miller M. and Siran J. Moore graphs and beyond: A survey of the degree/diameter problem. Electron. J. Combin., Dyn. Surv., 2005, no. DS14, 61 p.
Perez-Roses H. Algebraic and computer-based methods in the undirected degree/diameter problem - A brief survey. Electron. J. Graph Theory Appl., 2014, no. 2(2), pp. 166-190.
The Degree/Diameter Problem For Circulant Graphs. http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Circulant_Graphs.
Monakhova E. A., Romanov A. Yu., and Lezhnev E. V. Shortest path search algorithm in optimal two-dimensional circulant networks: Implementation for networks-on-chip. IEEE Access, 2020, no. 8, pp. 215010-215019.
Romanov A., Amerikanov A., and Lezhnev E. Analysis of approaches for synthesis of networks-on-chip by using circulant topologies. J. Physics. Conf. Series, 2018, vol. 1050, no. 1, pp. 1-12.
Monakhova E. A., Monakhov O. G., Romanov A. Yu., and 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, pp. 1-6.
Romanov A. Yu. and Starykh V. A. Routing in triple loop circulants: A case of networks-on-chip. Heliyon, 2020, no.6(7), pp. 1-7.
Ansari A. Q., Ansari M. R., and Khan M. A. Modified quadrant-based routing alglrithm for 3D torus network-on-chip architecture. Perspect. Sci., 2016, vol. 8, pp. 718-721.
Joseph J.M., Blochwitz C., Garcia-Ortiz A., and Pionteck T. Area and power savings via asymmetric organization of buffers in 3D-NoCs for heterogeneous 3D-SoCs. Microprocess. Microsyst., 2017, vol. 48, pp. 36-47.
Yebra J. L. A., Fiol M. A., Morillo P., and Alegre I. The diameter of undirected graphs associated to plane tessellations. Ars Combinatoria, 1985, no. 20B, pp. 159-171.
Martinez C., Stafford E., Beivide R., and Gabidulin E. M. Modeling hexagonal constellations with Eisenstein - Jacobi graphs. Problems Inform. Transmission, 2008, no. 44(1), pp. 1-11.
Barriere L., Fabrega J., Simo E., and Zaragoza M. Fault-tolerant routings in chordal ring networks. Networks, 2000, no. 36(3), pp. 180-190.
Liestman A. L., Opatrny J., and Zaragoza M. Network properties of double and triple fixed-step graphs. Int. J. Found. Comp. Sci., 1998, no. 9(1), pp. 57-76.
Jha P. K. A family of efficient six-regular circulants representable as a Kronecker product. Discr. Appl. Math., 2016, no. 203, pp. 72-84.
Parhami B. A class of odd-radix chordal ring networks. CS’J J. Comput. Sci. Eng., 2006, vol. 4, no. 2-4, pp. 1-9.
Dougherty R. and Faber V. The degree-diameter problem for several varieties of Cayley Graphs, 1: The Abelian case. SIAM J. Discr. Math., 2004, no. 17(3), pp. 478-519.
Monakhova E. A. Parametricheskoe zadanie serii semeystv analiticheski opisyvaemykh tsirkulyantnykh setey stepeni shest’ [A set of families of analytically described triple loop networks defined by a parameter]. Prikladnaya Diskretnaya Matematika, 2020, no. 49, pp. 108-119. (in Russian)
Monakhova E. A. and Monakhov O. G. Dinamicheskij algoritm parnoj marshrutizacii dlya analiticheski zadavaemyh semeystv cirkulyantnyh setey stepeni shest’ [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, pp. 30-37. (in Russian)
Series of families of degree six circulant graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 54. DOI: 10.17223/20710410/54/6
Download full-text version
Counter downloads: 71