Теорема Гринберга

Граф, негамильтоновость которого можно доказать с помощью теоремы Гринберга

Теорема Гринберга — необходимое условие для планарного графа, чтобы он содержал гамильтонов цикл, основанное на длинах циклов граней. Результат широко используется для построения негамильтоновых графов с дополнительными свойствами. Например, были построены новые контрпримеры гипотезе Тэйта (которую опроверг Татт в 1946 году). Теорему доказал латвийский математик Эмануэль Гринберг в 1968 году.

Формулировка

Пусть G — конечный планарный граф с гамильтоновым циклом C с фиксированным планарным вложением. Обозначим через ƒ_k и g_k число k-угольных граней вложения, которые находятся внутри и вне C соответственно. Тогда

$\sum _{k\geq 3}(k-2)(f_{k}-g_{k})=0.$

Эта формула является простым следствием формулы Эйлера.

Следствие этой теоремы — если планарный граф может быть вложен таким образом, что все грани, кроме одной, сравнимы с 2 по модулю 3, а одна грань не равна 2 по модулю 3, то граф не гамильтонов. Например, в графе на рисунке все грани имеют 5 или 8 сторон, а внешняя грань имеет 9 сторон, так что он удовлетворяет условию теоремы, а потому он не гамильтонов. Для любого планарного графа, грани, в которых число сторон сравнимо с 2 по модулю 3, дают 0 по модулю 3 в сумму в теореме Гринберга, поскольку множитель k − 2 в сумме для них обращается в нуль. Однако другие грани дают ненулевое по модулю 3 значение, независимо от того, находятся ли они внутри или вне гамильтонова цикла. И если имеется лишь одна такая грань, общая сумма не может быть нулевой и граф должен быть негамильтонов.

Приложения

Гринберг использовал свою теорему для поиска негамильтоновых кубических полиэдральных графов с высокой циклической рёберной связностью. Циклическая рёберная связность графа — это наименьшее число рёбер, которое можно удалить так, чтобы оставшийся граф содержал более чем одну циклическую компоненту. Граф Татта с 46 вершинами и меньшие кубические негамильтоновы полиэдральные графы, полученные из него, имеют циклическую рёберную связность три. Гринберг использовал свою теорию для поиска негамильтонова кубического полиэдрального графа с 44 вершинами, 24 гранями и циклической рёберной связностью четыре, а также другого примера (показанного на рисунке) с 46 вершинами, 25 гранями и циклической рёберной связностью пять, максимально возможной рёберной связностью для кубических планарных графов, отличных от K₄. В приведённом примере все ограниченные грани имеют пять или восемь рёбер, в обоих случаях число граней сравнимо с 2 по модулю 3, но внешняя грань имеет девять рёбер, что даёт ненулевой вклад в формуле в теореме Гринберга по модулю 3. Таким образом, граф не может быть гамильтоновым.

Теорема Гринберга используется также для поиска планарных гипогамильтоноввых графов, снова путём построения графа, в котором все грани имеют число рёбер, сравнимых с 2 по модулю 3. Томассен использовал теорему несколько более сложным образом, чтобы найти планарный кубический гипогамильтонов граф — построенный им граф включает грань с 4 рёбрами, смежную граням с 7 рёбрами, а все остальные грани имеют пять или восемь рёбер. Чтобы граф удовлетворял теореме Гринберга, нужно было бы отделить одну из граней с 4 или 7 рёбрами от остальных четырёх, что невозможно.

Ограничения

Существуют планарные негамильтоновы графы, в которых все грани имеют пять или восемь сторон. Для этих графов формула Гринберга, взятая по модулю три, всегда удовлетворяет любому разбиению граней на два подмножества, что не даёт использовать теорему для доказательства негамильтоновости в этом случае (Zaks 1977).

Невозможно использовать теорему Гринберга для поиска контрпримеров гипотезе Барнетта, что любой кубический двудольный полиэдральный граф гамильтонов. В этих графах всегда существует разбиение граней на два подмножества, удовлетворяющих теореме Гринберга, независимо от гамильтоновости (Krooss 2004).

Ссылки

• Grinberg Graphs // MathWorld.