ГлавнаяАрхивК вопросу о максимально достижимом числе вершин циркулянтных графов при любом диаметре

К вопросу о максимально достижимом числе вершин циркулянтных графов при любом диаметре | Прикладная дискретная математика. 2014. № 3 (25).

Рассматривается задача о максимально достижимом числе вершин при заданных размерности и диаметре неориентированных циркулянтных графов. В 1994 г. Ф.П. Муга доказал теорему о том, что это число является нечётным при любых размерностях и диаметрах циркулянтного графа, что подтверждается для одно-, двух- и трёхмерных циркулянтов. В настоящей работе доказано, что найденное доказательство теоремы некорректно. На основании новых данных скорректирована таблица максимально достижимых порядков циркулянтов размерности четыре.
  • Title К вопросу о максимально достижимом числе вершин циркулянтных графов при любом диаметре
  • Headline К вопросу о максимально достижимом числе вершин циркулянтных графов при любом диаметре
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3 (25)
  • Date:
  • DOI
Ключевые слова
diameter, maximum order of a graph, undirected circulant graphs, максимальный порядок графа, диаметр, неориентированные циркулянтные графы
Авторы
Ссылки
Монахова Э.А. О построении циркулянтных сетей размерности четыре с максимальным числом вершин при любом диаметре // Прикладная дискретная математика. 2013. №3(21). С. 76-85.
Muga F. P. Undirected circulant graphs // Inter. Symp. on Parallel Architectures, Algorithms and Networks. IEEE, 1994. P. 113-118.
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. Triple circulant communication networks of parallel computer systems // Optoelectronics, Instrumentation and Data Processing. N. Y.: Allerton Press Inc., 2006. No. 3. P. 90-101.
Chen S. and Jia X.-D. Undirected loop networks // Networks. 1993. No. 23. P. 257-260.
Monakhova E. A. Optimal triple loop networks with given transmission delay: topological design and routing // Inter. Network Optimization Conf. (INOC'2003). Evry/Paris, France. 2003. P. 410-415.
Golomb S. W. and Welch L. R. Perfect codes in the Lee metric and the packing of polyominoes // SIAM J. Appl. Math. 1970. V. 18. No. 2. P. 302-317.
Costa S. I. R., Strapasson J. E., Alves M. M. S., and Carlos T. B. Circulant graphs and tessellations on flat tori // Linear Algebra Applicat. 2010. V.432. No. 1. P. 369-382.
Lewis R. R. The degree-diameter problem for circulant graphs of degree 8 and 9 // Electron. J. Combinator. http://web.ArXiv.org/1404.3948.pdf, 20 April 2014.
Horak P. Tilings in Lee metric // Eur. J. Combinator. 2009. No. 30. P. 480-489.
Hwang F. K. A survey on multi-loop networks // Theor. Comput. Sci. 2003. No. 299. P. 107-121.
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.
Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. №3(13). С. 92-115.
К вопросу о максимально достижимом числе вершин циркулянтных графов при любом диаметре | Прикладная дискретная математика. 2014. № 3 (25).
К вопросу о максимально достижимом числе вершин циркулянтных графов при любом диаметре | Прикладная дискретная математика. 2014. № 3 (25).