Том 20, номер 1, 2013 г., Стр. 37-44

УДК 519.87
Монахова Э. А.
Новая достижимая нижняя оценка числа вершин в циркулянтных сетях размерности четыре

Аннотация:
Рассматривается задача оптимизации неориентированных циркулянтных сетей, состоящая в максимизации числа вершин при заданных степени и диаметре графа. Получена новая нижняя оценка достижимого числа вершин циркулянтных сетей размерности четыре и диаметров $d\equiv0\pmod4$, улучшенная на $O(d^3)$ по сравнению с наилучшей известной. Построено бесконечное семейство циркулянтов, достигающих найденной оценки. Найденные графы, как предполагаем, являются максимально возможными циркулянтами размерности четыре.
Табл. 2, библиогр. 9.

Ключевые слова: неориентированная циркулянтная сеть, диаметр, максимальный порядок графа.

Монахова Эмилия Анатольевна ^1,2
1. Институт вычислительной математики и математической геофизики СО РАН,
пр. Aкад. Лаврентьева, 6, 630090 Новосибирск, Россия
е-mail: emilia@rav.sscc.ru

Статья поступила 23 апреля 2012 г.
Исправленный вариант — 21 сентября 2012 г.

Литература

[1] Монахова Э. А. Оптимизация циркулянтных сетей связи размерности четыре // Дискрет. анализ и исслед. операций. - 2008. - Т. 15, №3. - С. 58–64.

[2] Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикл. дискрет. математика. - 2011. - T. 13, №3. - С. 92–115.

[3] Bermond J.-C., Comellas F., Hsu D. F. Distributed loop computer networks: a survey // J. Parallel Distrib. Comput. - 1995. - Vol. 24. - P. 2–10.

[4] Chen S., Jia X.-D. Undirected loop networks // Networks. - 1993. - Vol. 23. - P. 257–260.

[5] Dougherty R., Faber V. The degree-diameter problem for several varieties of Cayley graphs. 1: The abelian case // SIAM J. Discrete Math. - 2004. - Vol. 17, N 3. - P. 478–519.

[6] Hwang F. K. A survey on multi-loop networks // Theoret. Comput. Sci. - 2003. - Vol. 299. - P. 107–121.

[7] Macbeth H., Siagiova J., Siran J. Cayley graphs of given degree and diameter for cyclic, abelian, and metacyclic groups // Discrete Math. - 2012. - Vol. 312, N 1. - P. 94–99.

[8] Monakhova E. Optimal triple loop networks with given transmission delay: topological design and routing // Proc. Int. Network Optimization Conf. INOC’2003. - Evry/Paris, France: Institut National des Telecommunications, 2003. - P. 410–415.

[9] Wong C. K., Coppersmith D. A combinatorial problem related to multimodule memory organizations // J. Assoc. Comput. Mach. - 1974. - Vol. 21. - P. 392–402.