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

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

Впервые была высказана Вадимом Визингом. Утверждение гипотезы гласит, что для $\mathrm{\gamma <!--\; \gamma \; -->}(G)$$\gamma (G)$ — минимального числа вершин в доминирующем множестве графа $G$$G$, выполнено:

$\mathrm{\gamma <!--\; \gamma \; -->}(G\mathrm{◻<!--\; ◻\; -->}H)⩾<!--\; ⩾\; -->\mathrm{\gamma <!--\; \gamma \; -->}(G)\mathrm{\gamma <!--\; \gamma \; -->}(H)$$\gamma (G\,\square \,H)\geqslant \gamma (G)\,\gamma (H)$.

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

ПримерыПравить

 

Оптимальное доминирующее множество произведения двух звёзд $K_{1,4}\mathrm{◻<!--\; ◻\; -->}{K}_{1,4}$$K_{1,4}\,\square \,K_{1,4}$ , содержащее пять вершин. Примеры, подобные этому, показывают, что для некоторых произведений графов оценка в гипотезе Визинга может быть далека от точной

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

Доминирующее число произведения может быть существенно больше границы, данной в гипотезе Визинга. Например, для звезды K_1,n доминирующее число γ(K_1,n) равно единице — всего одна центральная вершина доминирует над всем графом. Для графа G = K_1,n ◻ K_1,n, образованного произведение двух звёзд, гипотеза Визинга утверждает, что доминирующее число не меньше 1 × 1 = 1. Однако, на самом деле, доминирующее множество много больше. Граф содержит n² + 2n + 1 вершин — n² получаем из листьев двух сомножителей, 2n получаем из произведения листьев на центр, и одна вершина получается произведением центров. Каждое произведение листа на центр доминирует в точности над n лист-лист вершинами произведения, так что n лист-центр вершин нужно для доминирования над всеми лист-лист вершинами. Однако, ни одна вершина лист-центр не доминирует над такой же другой вершиной, так что даже в случае выбора n вершин лист-центр в доминирующее множество, остаётся n недоминируемых лист-центр вершин, которые доминируются одной центр-центр вершиной. Таким образом, доминирующее число этого графа равно γ(K_1,n ◻ K_1,n) = n + 1, что много больше тривиальной границы, которую даёт гипотеза Визинга.

Существует бесконечное число семейство произведений графов, для которых оценка в гипотезе Визинга точна. Например, если G и H оба являются связными графами и каждый имеет по меньшей мере четыре вершины и число вершин в точности вдвое больше доминирующего числа, то γ(G ◻ H) = γ(G)γ(H). Графы G и H с таким свойством содержат цикл C₄ с четырьмя вершинами вместе с корневым произведением связного графа и одиночного ребра.

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

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

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

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

Верхние границыПравить

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

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

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

ЛитератураПравить

• 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.

СсылкиПравить

• Weisstein, Eric W. Vizing Conjecture (англ.) на сайте Wolfram MathWorld.