For undirected circulant networks, the maximization problem for the number of nodes under given degree and diameter of a graph is considered. A new lower estimate is obtained for the attainable number of nodes in the circulant graphs of dimension 4 and any diameter. Some new infinite families of circulants reaching this estimate are constructed. For graphs of these families, some analytical descriptions are given.
Download file
Counter downloads: 100
- Title On a construction of quadruple circulant networks with the maximal number of nodes for any diameter
- Headline On a construction of quadruple circulant networks with the maximal number of nodes for any diameter
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(21)
- Date:
- DOI
Keywords
неориентированные циркулянтные сети, диаметр, максимальный порядок графа, undirected circulant graphs, diameter, maximum order of a graphAuthors
References
Монахова Э. А. Новая достижимая нижняя оценка числа вершин в циркулянтных сетях размерности четыре // Дискретный анализ и исследование операций. 2013. Т. 20. №1. С.37-44.
Монахова Э.А. Оптимизация циркулянтных сетей связи размерности четыре // Дискретный анализ и исследование операций. 2008. Т. 15. №3. С. 58-64.
Dougherty R. and Faber V. The degree-diameter problem for several varieties of Cayley graphs, 1: the Abelian case // SIAM J. Discrete Math. 2004. V. 17. No.3. P. 478-519.
Monakhova E. A. Optimal triple loop networks with given transmission delay: topological design and routing // Inter. Network Optimization Conf. (IN0C'2003), Evry/Paris, France. 2003. P. 410-415.
Jia X.-D. and Su W. Triple loop networks with minimal transmission delay // Int. J. Found. Comp. Sci. 1997. V. 8. No. 3. P. 305-328.
Chen S. and Jia X.-D. Undirected loop networks // Networks. 1993. No. 23. P. 257-260.
Macbeth H., Siagiova J., and Siran J. Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups // Discrete Math. 2012. V.312. No. 1. P. 94-99.
Корнеев В. В. О макроструктуре однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1974. №60. С. 17-34.
Wong C.K. and Coppersmith D. A combinatorial problem related to multimodule memory organizations // J. Assoc. Comp. Mach. 1974. No. 21. P. 392-402.
Воробьев В. А. Простейшие структуры однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1974. №60. С. 35-49.
Stojmenovic I. Multiplicative circulant networks. Topological properties and communication algorithms // Discrete Appl. Math. 1997. No. 77. P. 281-305.
Muga F. P., Saldana R. P., and Yu W. E. S. Building graph-based symmetric cluster // NECTEC Techn. J. 2001. V. 11. No. 9. P. 195-199.
Narayanan L., Opatrny J., and Sotteau D. All-to-all optical routing in chordal rings of degree four // Algorithmica. 2001. V.31. No. 2. P. 155-178.
Comellas F., Mitjana M., and Peters J. G. Broadcasting in small-world communication networks // 9th Inter. Coll. on Structural Information and Communication Complexity (SIROCCO 9), 2002. Proc. Informatics. 2002. No. 13. P. 73-85.
Martinez C., Beivide R., and Gabidulin E. M. Perfect codes from Cayley graphs over Lipschitz integers // IEEE Trans. Inform. Theory. 2009. V.55. No. 8. P. 3552-3562.
Нестеренко Б. Б., Новотарский М. А. Клеточные нейронные сети на циркулянтных графах // Искусственный интеллект. 2009. №3. С. 132-138.
Bermond J.-C., Comellas F., and Hsu D. F. Distributed loop computer networks: a survey // J. Parallel Distributed Comput. 1995. V.24. P. 2-10.
Hwang F. K. A survey on multi-loop networks // Theor. Comp. Sci. 2003. No. 299. P. 107-121.
Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. №3(13). С. 92-115.
On a construction of quadruple circulant networks with the maximal number of nodes for any diameter | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 3(21).
Download full-text version
Download fileCounter downloads: 319