For circulant networks, the problem of the maximal attainable number of nodes under given degree and diameter of their graphs is considered. A research of multiplicative circulant networks with generators in the form of (1, t, t2,... ,tk-1) for odd t ^ 5 is presented. On the base of this research, two new families of multiplicative circulant networks of orders n = (t + 1)(1 + t + ... + tk-1)/2 + tk-1 for odd dimensions k ^ 3 and diameters d = 0 mod k and even dimensions k ^ 4 and diameters d = 0 mod k and d = 0 mod k/2 are constructed. The orders of these graphs are larger than orders of graphs of all known families of multiplicative circulant networks under the same dimensions and diameters.
Download file
Counter downloads: 174
- Title New families of multiplicative circulant networks
- Headline New families of multiplicative circulant networks
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 41
- Date:
- DOI 10.17223/20710410/41/8
Keywords
мультипликативные циркулянтные сети, диаметр, максимальный порядок графа, multiplicative circulant networks, diameter, maximum order of a graphAuthors
References
Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. №3. С. 92-115.
Monakhova E. A. A survey on undirected circulant graphs // Discr. Math., Algorithms and Appl. 2012. No.4(1). P. 17-47.
Perez-Roses H. Algebraic and computer-based methods in the undirected degree/diameter problem - a bief survey // Electronic J. Graph Theory and Appl. 2014. No. 2(2). P. 166-190.
Erickson A., Stewart I. A., Navaridas J., and Kiasari A. E. The stellar transformation: From interconnection networks to datacenter networks // Comput. Networks. 2017. No. 113. P. 29-45.
Wong C. K. and Coppersmith D. A combinatorial problem related to multimodule memory organizations // J. Assoc. Comput. Mach. 1974. No. 21. P. 392-402.
Monakhova E. Optimal triple loop networks with given transmission delay: Topological design and routing // Intern. Network Optimization Conf. (IN0C'2003), Evry/Paris, France, 2003. P. 410-415.
Dougherty R. and Faber V. The degree-diameter problem for several varieties of Cayley graphs, 1: The Abelian case // SIAM J. Discrete Math. 2004. No. 17(3). P. 478-519.
Lewis R. The degree-diameter problem for circulant graphs of degree 8 and 9 // arXiv:1404.3948v1, 2014.
Feria-Puron R., Ryan J., and Perez-Roses H. Searching for large multi-loop networks // Elec. Notes Disc. Math. 2014. No. 46. P. 233-240.
Feria-Puron R., Perez-Roses H., and Ryan J. Searching for large circulant graphs // arXiv:1503.07357v1 [math.CO] (25 Mar 2015). P. 31.
The Degree/Diameter Problem For Circulant Graphs. http://combinatoricswiki.org/ wiki/The_Degree_Diameter_Problem_for_Circulant_Graphs.
Chen S. and Jia X. -D. Undirected loop networks // Networks. 1993. No. 23. P. 257-260.
Parhami B. Chordal rings based on symmetric odd-radix number systems // Proc. Intern. Conf. on Communications in Computing (Las Vegas, NV, June 27-30). Los Alamitos: IEEE Press, 2005. P. 196-199.
Parhami B. A class of odd-radix chordal ring networks // The CS'J J. Comput. Sci. Eng. 2006. Vol. 4. No. 2-4. P. 1-9.
Stojmenovic I. Multiplicative circulant networks. Topological properties and communication algorithms // Discr. Appl. Math. 1997. Vol.77. P.281-305.
Monakhova E. A. On an extremal family of circulant networks // J. Appl. Industr. Math. 2011. No. 5(4). P. 1-7.
New families of multiplicative circulant networks | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 41. DOI: 10.17223/20710410/41/8
Download full-text version
Counter downloads: 574