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

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

\gamma (G\,\Box \,H)\geq \gamma (G)\gamma (H).\,

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

Примеры

4- цикл $C 4$ имеет доминирование номер два: любая отдельная вершина доминирует только над собой и двумя своими соседями, но любая пара вершин доминирует над всем графом. Произведение $C 4 □ C 4$ представляет собой четырёхмерный граф гиперкуба ; у него 16 вершин, и любая отдельная вершина может доминировать только над собой и четырьмя соседями, поэтому три вершины могут доминировать только над 15 из 16 вершин. Следовательно, чтобы доминировать во всем графе, требуется как минимум четыре вершины - граница, определяемая гипотезой Визинга.

Число доминирования продукта может быть намного больше, чем граница, определяемая гипотезой Визинга. Например, для звезды $K 1, n$ ее число доминирования $γ(K 1, n)$ равно единице: можно доминировать над всей звездой с единственной вершиной в ее центре. Следовательно, для графа $G = K 1, n □ K 1, n,$ сформированного как произведение двух звезд, гипотеза Визинга утверждает лишь, что число доминирования должно быть не менее $1 \times 1 = 1$ . Однако число доминирования в этом графе на самом деле намного выше. У него есть $н 2 + 2 n + 1$ вершина: $n 2$ образовано из произведения листа в обоих факторах, $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 4$ вместе с корневыми произведениями связного графа и одного ребра. ^{[ 2 ]}

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

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

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

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

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

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

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

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

Примечания

Ссылки

Баркалкин, AM; Герман, LF (1979), "Число внешней устойчивости декартова произведения графов", Bul. Акад. Stiince RSS Moldoven (на русском языке), 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 .
Финк, Дж. Ф.; Джейкобсон, MS; Кинч, Л.Ф.; Робертс, Дж. (1985), «О графах, имеющих доминирование половины их порядка», Период. Математика. Венгрия. , 16 (4): 287–293, doi : 10.1007/BF01848079 , MR 0833264 .
Гравье, С.; Хеллади, А. (1995), «О числе доминирования векторных произведений графов», Discrete Mathematics , 145 (1–3): 273–277, doi : 10.1016/0012-365X(95)00091-A , MR 1356600 .
Хартнелл, БЛ; Ралл, Д.Ф. (1991), «О гипотезе Визинга», Congr. Число. , 82 : 87–96, МР 1152060 .
Джейкобсон, MS; Кинч, LF (1986), «О доминировании произведений графов II: деревья», Journal of Graph Theory , 10 : 97–106, doi : 10.1002/jgt.3190100112 , MR 0830061 .
Клавжар, Санди; Змазек, Б. (1996), «О гипотезе Визинга для графов прямых произведений», Discrete Mathematics , 156 (1–3): 243–246, doi : 10.1016/0012-365X(96)00032-5 , MR 1405022 .
Паян, К.; Сюонг, Нью-Хэмпшир (1982), «Графы, сбалансированные по доминированию», Журнал теории графов , 6 : 23–32, doi : 10.1002/jgt.3190060104 , MR 0644738 .
Визинг В.Г. (1968), "Некоторые нерешенные задачи теории графов", Успехи матем. Наук , 23 (6): 117–134, МР 0240000 .

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

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

[1] Паян и Сюонг (1982) ; Финк и др. (1985) ; Джейкобсон и Кинч (1986) ; Хартнелл и Ралл (1991) .

[fjkr-2] Jump up to: ^а ^б Финк и др. (1985) .

[3] Джейкобсон и Кинч (1986) ; Эль-Захар и Парик (1991) .

[4] Баркалкин и Герман (1979) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]