Догадка Визинга

Предложение о доминирующем числе декартовых произведений графов

В теории графов гипотеза Визинга касается связи между числом доминирования и декартовым произведением графов . Эта гипотеза была впервые высказана Вадимом Г. Визингом  (1968) и утверждает, что если γ( G ) обозначает минимальное число вершин в доминирующем множестве для графа G , то

${\displaystyle \gamma (G\,\Box \,H)\geq \gamma (G)\gamma (H).\,}$

Gravier & Khelladi (1995) предположили аналогичную границу для числа доминирования тензорного произведения графов ; однако, контрпример был найден Klavžar & Zmazek (1996). С тех пор как Визинг предложил свою гипотезу, многие математики работали над ней, и частичные результаты описаны ниже. Более подробный обзор этих результатов см. в Brešar et al. (2012).

Примеры

Оптимальное доминирующее множество из пяти вершин в произведении двух звезд, K _1,4 □ 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 ² + 2 n + 1 вершин: n ² образовано из произведения листа в обоих множителях, 2 n из произведения листа в одном множителе и хаба в другом множителе, и одна оставшаяся вершина образована из произведения двух хабов. Каждая вершина произведения лист-концентратор в G доминирует ровно над n вершинами лист-концентратор, поэтому для доминирования над всеми вершинами лист-концентратор требуется n вершин лист-концентратор. Однако ни одна вершина лист-концентратор не доминирует над любой другой такой вершиной, поэтому даже после того, как n вершин лист-концентратор выбраны для включения в доминирующий набор, остается еще n недоминируемых вершин лист-концентратор, которые могут доминироваться одной вершиной хаб-концентратор. Таким образом, число доминирования этого графа равно γ( K _{1, n} □ K _{1, n} ) = n + 1, что намного выше тривиальной границы единицы, заданной гипотезой Визинга.

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

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

Очевидно, гипотеза верна, когда либо G , либо H имеет доминирование номер один: так как произведение содержит изоморфную копию другого фактора, доминирование которого требует по крайней мере γ( G )γ( H ) вершин.

Известно также, что гипотеза Визинга верна для циклов ^[3] и для графов с доминированием номер два. ^[4]

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

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

Визинг (1968) заметил, что

${\displaystyle \gamma (G\,\Box \,H)\leq \min\{\gamma (G)|V(H)|,\gamma (H)|V(G)|\}.}$

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

Примечания

1. Пайан и Сюонг (1982); Финк и др. (1985); Якобсон и Кинч (1986); Хартнелл и Ралл (1991).
2. Финк и др. (1985).
3. Джейкобсон и Кинч (1986); Эль-Захар и Парик (1991).
4. Баркалкин и Герман (1979).

Ссылки

• Баркалкин, AM; Герман, LF (1979), "Число внешней устойчивости декартова произведения графов", Бюл. АН Молдовы , 1 : 5–8, MR  0544028.
• Брешар, Боштян; Дорбек, Пол; Годдард, Уэйн; Хартнелл, Берт Л.; Хеннинг, Майкл А.; Клавжар, Санди; Ралл, Дуглас Ф. (2012), «Гипотеза Визинга: обзор и последние результаты», Journal of Graph Theory , 69 (1): 46–76, doi : 10.1002/jgt.20565, MR  2864622.
• Кларк, В. Эдвин; Суен, Стивен (2000), «Неравенство, связанное с гипотезой Визинга», Электронный журнал комбинаторики , 7 (1): N4, doi :10.37236/1542, MR  1763970.
• Эль-Захар, М.; Парик, CM (1991), «Число доминирования произведений графов», Ars Combinatoria , 31 : 223–227, MR  1110240.
• Финк, Дж. Ф.; Якобсон, М. С.; Кинч, Л. Ф.; Робертс, Дж. (1985), «О графах, имеющих доминирующее число в два раза меньше их порядка», Period. Math. Hungar. , 16 (4): 287–293, doi :10.1007/BF01848079, MR  0833264.
• Гравье, С.; Хеллади, А. (1995), «О числе доминирования перекрестных произведений графов», Дискретная математика , 145 (1–3): 273–277, doi : 10.1016/0012-365X(95)00091-A , MR  1356600.
• Хартнелл, Б. Л.; Ралл, Д. Ф. (1991), «О гипотезе Визинга», Congr. Numer. , 82 : 87–96, MR  1152060.
• Якобсон, М.С.; Кинч, Л.Ф. (1986), «О доминировании произведений графов II: деревья», Журнал теории графов , 10 : 97–106, doi :10.1002/jgt.3190100112, MR  0830061.
• Клавжар, Санди; Змазек, Б. (1996), «О гипотезе типа Визинга для графов прямых произведений», Дискретная математика , 156 (1–3): 243–246, doi : 10.1016/0012-365X(96)00032-5 , MR  1405022.
• Payan, C.; Xuong, NH (1982), «Графы с балансом доминирования», Журнал теории графов , 6 : 23–32, doi :10.1002/jgt.3190060104, MR  0644738.
• Визинг, В.Г. (1968), «Некоторые нерешенные проблемы теории графов», УМН , 23 (6): 117–134, МР  0240000.

Внешние ссылки

• Вайсштейн, Эрик В. «Гипотеза Визинга». MathWorld .