Гипотеза Визинга

Гипотеза Визинга — предположение о связи доминирующего множества и прямого произведения графов. По состоянию на 2017 год она остаётся недоказанной в общем случае, однако установлена для ряда частных классов графов.

Гипотеза впервые была высказана Вадимом Визингом[1]. Её утверждение гласит, что для — минимального числа вершин в доминирующем множестве графа — выполнено неравенство

.

В 1995 году[2] были предложены аналогичные границы для доминирующего числа тензорного произведения графов, однако позднее[3] был найден контрпример.

Примеры

Доминирующее число цикла с четырьмя вершинами C4 равно двум: любая отдельная вершина доминирует над собой и двумя соседями, а любая пара вершин доминирует над всем графом. Произведение C4 ◻ C4 является графом четырёхмерного гиперкуба. Он имеет 16 вершин, и каждая вершина доминирует над собой и четырьмя соседями; следовательно, три вершины могут доминировать лишь над 15 из 16 вершин. Таким образом, минимальное доминирующее множество имеет размер не менее четырёх — как раз то число, которое предсказывается гипотезой Визинга.

Доминирующее число произведения графов может быть существенно больше границы, указанной в гипотезе. Например, для звезды K1,n доминирующее число равно единице: центральная вершина доминирует над всеми листьями. Для графа G = K1,n ◻ K1,n, образованного произведением двух звёзд, гипотеза Визинга даёт нижнюю границу 1 × 1 = 1. Однако фактическое доминирующее множество значительно больше.

Граф содержит n2 + 2n + 1 вершину: n2 возникает из пар лист-лист двух сомножителей, 2n — из произведений листа на центр, и одна вершина — из произведения двух центров. Каждая вершина типа «лист–центр» доминирует над n вершинами типа «лист–лист», поэтому n таких вершин необходимо для доминирования над всеми лист-лист вершинами. Однако ни одна вершина типа «лист–центр» не доминирует над другой вершиной того же типа, поэтому после выбора n таких вершин остаются n недоминируемых лист-центр вершин. Все они доминируются единственной вершиной «центр–центр». Таким образом, доминирующее число произведения равно γ(K1,n ◻ K1,n) = n + 1, что значительно превышает тривиальную границу.

Существует бесконечное семейство произведений графов, для которых оценка в гипотезе Визинга достигается точно[4][5][6][7]. В частности, если G и H — связные графы, каждый из которых имеет не менее четырёх вершин, а общее число вершин каждого графа в точности в два раза превышает его доминирующее число, то γ(G ◻ H) = γ(G)γ(H)[8]. Такие графы содержат цикл C4 и могут быть представлены как корневое произведение связного графа и одиночного ребра[8].

Частичные результаты

Гипотеза очевидным образом выполняется, если хотя бы один из графов G или H имеет доминирующее число 1: произведение содержит изоморфную копию второго графа, так что его доминирующее множество имеет по меньшей мере γ(G)γ(H) элементов.

Известно, что гипотеза Визинга выполняется для циклов[6][9] и для графов с доминирующим числом два[10].

В 2000 году[11] было доказано, что доминирующее число произведения по меньшей мере равно половине значения, указанного в гипотезе, для любых графов G и H.

Верхние границы

Визинг в оригинальной статье [1] отметил, что

γ(G ◻ H) ≤ min{γ(G)|V(H)|, γ(H)|V(G)|}.

Доминирующее множество, достигающее этой границы, можно получить как прямое произведение доминирующего множества одного из графов G или H с множеством всех вершин другого графа.

Примечания

  1. ↑ 1 2 Визинг, 1968.
  2. ↑ Gravier, Khelladi, 1995.
  3. ↑ Klavžar, Zmazek, 1996.
  4. ↑ Payan, Xuong, 1982.
  5. ↑ Fink, Jacobson, Kinch, Roberts, 1985.
  6. ↑ 1 2 Jacobson, Kinch, 1986.
  7. ↑ Hartnell, Rall, 1991.
  8. ↑ 1 2 Fink, Jacobson, Kinch, Roberts, 1985.
  9. ↑ El-Zahar, Pareek, 1991.
  10. ↑ Барцалкин, Герман, 1979.
  11. ↑ Clark, Suen, 2000.

Литература

  • A. M. Барцалкин, Л. Ф. Герман. Внешнее число устойчивости прямого произведения графов // Известия АН МССР. — 1979. — Т. 1. — С. 5–8.
  • W. Edwin Clark, Stephen Suen. Inequality related to Vizing's conjecture // Electronic Journal of Combinatorics. — 2000. — Т. 7, вып. 1. — С. N4.
  • M. El-Zahar, C. M. Pareek. Domination number of products of graphs // Ars Combin.. — 1991. — Т. 31. — С. 223–227.
  • J. F. Fink, M. S. Jacobson, L. F. Kinch, J. Roberts. On graphs having domination number half their order // Period. Math. Hungar.. — 1985. — Т. 16, вып. 4. — С. 287–293. — doi:10.1007/BF01848079.
  • S. Gravier, A. Khelladi. On the domination number of cross products of graphs // Discrete Mathematics. — 1995. — Т. 145. — С. 273–277. — doi:10.1016/0012-365X(95)00091-A.
  • B. L. Hartnell, D. F. Rall. On Vizing's conjecture // Congr. Numer.. — 1991. — Т. 82. — С. 87–96.
  • Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8.
  • M. S. Jacobson, L. F. Kinch. On the domination of the products of graphs II: trees // J. Graph Theory. — 1986. — Т. 10. — С. 97–106. — doi:10.1002/jgt.3190100112.
  • Sandi Klavžar, B. Zmazek. On a Vizing-like conjecture for direct product graphs // Discrete Mathematics. — 1996. — Т. 156. — С. 243–246. — doi:10.1016/0012-365X(96)00032-5.
  • C. Payan, N. H. Xuong. Domination-balanced graphs // J. Graph Theory. — 1982. — Т. 6. — С. 23–32. — doi:10.1002/jgt.3190060104.
  • В. Г. Визинг. Некоторые нерешенные задачи в теории графов // Успехи математических наук. — 1968. — Т. 23, вып. 6. — С. 117–134.

Ссылки

Эта статья взята у (из) Википедия. Текст лицензируется по Creative Commons Attribution-Share Alike 4.0. К медиа файлам могут применятся дополнительные условия.