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

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

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

.

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

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

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

Доминирующее число произведения может быть существенно больше границы, данной в гипотезе Визинга. Например, для звезды K1,n доминирующее число γ(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]. Графы G и H с таким свойством содержат цикл 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. Визинг, 1968.
  2. Gravier, Khelladi, 1995.
  3. Klavžar, Zmazek, 1996.
  4. Payan, Xuong, 1982.
  5. Fink, Jacobson, Kinch, Roberts, 1985.
  6. Jacobson, Kinch, 1986.
  7. Hartnell, Rall, 1991.
  8. 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.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.