Гипотеза Визинга — предположение о связи доминирующего множества и прямого произведения графов, не подтверждённое по состоянию на 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 с множеством всех вершин другого графа.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .