Гипотеза Визинга — предположение о связи доминирующего множества и прямого произведения графов. По состоянию она остаётся недоказанной в общем случае, однако установлена для ряда частных классов графов.
Гипотеза впервые была высказана Вадимом Визингом. Её утверждение гласит, что для — минимального числа вершин в доминирующем множестве графа — выполнено неравенство .
В 1995 году были предложены аналогичные границы для доминирующего числа тензорного произведения графов, однако позднее был найден контрпример.
Примеры
Доминирующее число цикла с четырьмя вершинами 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, что значительно превышает тривиальную границу.
Существует бесконечное семейство произведений графов, для которых оценка в гипотезе Визинга достигается точно. В частности, если G и H — связные графы, каждый из которых имеет не менее четырёх вершин, а общее число вершин каждого графа в точности в два раза превышает его доминирующее число, то γ(G ◻ H) = γ(G)γ(H).. Такие графы содержат цикл C4 и могут быть представлены как корневое произведение связного графа и одиночного ребра.
Частичные результаты Гипотеза очевидным образом выполняется, если хотя бы один из графов G или H имеет доминирующее число 1: произведение содержит изоморфную копию второго графа, так что его доминирующее множество имеет по меньшей мере γ(G)γ(H) элементов.
Известно, что гипотеза Визинга выполняется для циклов и для графов с доминирующим числом два.
В 2000 году было доказано, что доминирующее число произведения по меньшей мере равно половине значения, указанного в гипотезе, для любых графов G и H.
Верхние границы Визинг в оригинальной статье отметил, что γ(G ◻ H) ≤ min{γ(G)|V(H)|, γ(H)|V(G)|}. Доминирующее множество, достигающее этой границы, можно получить как прямое произведение доминирующего множества одного из графов G или H с множеством всех вершин другого графа.
Примечания
Литература
Ссылки
Категория:Теория графов Категория:Математические гипотезы