Розкладність графів. Квазігамільтонові Графи

Скінченний зв'язний граф Gr(V,E) з множиною вершин V=V(Gr) і множиною ребер E=E(Gr), називається гамільтоновим, якщо існує така нумерація f: {1,2,...,n}V множини його вершин, що

d(f(1),f(2))=d(f(2),f(3))=...=d(f(n-1),f(n))=d(f(n),f(1))=1.

При цьому послідовність f(1),f(2),…,f(n) називається гамільтоновим циклом. Задача характеризації гамільтонових графів - одна з найвідоміших нерозв'язаних проблем теорії графів (див. [5, стор. 85], [12, стор. 72]).

За теоремою 4.1 множину вершин довільного скінченного звязного графа Gr(V,E) можна занумерувати f: {1,2,...,n}V так, що

d(f(1),f(2))3, d(f(2),f(3))3, ..., d(f(n-1), f(n))3, d(f(n), f(1))3.

Послідовність вершин f(1),f(2),…,f(n) називається повним квазіциклом графа. У зв'язку з цим твердженням природно виникають такі означення і проблеми.

Означення 1. Нумерацію f: {1,2,...,n}V множини вершин скінченного зв'язного графа Gr(V,E) назвемо квазігамільтоновим циклом (скорочено qh-циклом), якщо

d(f(1),f(2)) 2, d(f(2),f(3)) 2, ..., d(f(n-1),f(n)) 2, d(f(n),f(1)) 2.

Граф, що допускає таку нумерацію вершин назвемо квазігамільтоновим графом (скорочено qhc-графом).

Означення 2. Нумерацію f: {1,2,...,n}V множини вершин скінченного зв'язного графа Gr(V,E) назвемо квазігамільтоновим шляхом (скорочено qh-шляхом), якщо

d(f(1),f(2))2, d(f(2),f(3))2, ..., d(f(n-1),f(n))2.

Граф, що допускає таку нумерацію вершин, назвемо qhp-графом.

Проблема 1. Охарактеризувати qhc-графи.

Проблема 2. Охарактеризувати qhp-графи.

В цьому параграфі проблеми 1 та 2 розв'язано для дерев, доведено аналог теореми Дірака для для qhc-графів, а також розглянуто деякі варіанти проблеми 2 для нескінченних графів.

Нехай T(V,E) - скінченне дерево, xV, B(x,1)={x,y1,y2,...,ym}. Після видалення вершини x і ребер {x,y1}, {x,y2},..., {x,ym} дерево T розпадається на дерева , , ... , з коренями y1, y2 ,..., ym . Множину цих дерев позначимо (x)={ , , ... , }.

Лема 1. Нехай T(V,E)- скінченне дерево,

xV, (x)=},

V( )1, V( ), ..., V( )1, V( ) ... = V( )=1.

Якщо T - ghc-граф, то k2.

Доведення. Припустимо супротивне k2 і зафіксуємо gh-цикл x=x0, x1, x2, ..., xn-1 в дереві T. 3 послідовності x0, x1, x2, ..., xn-1 викреслимо всі вершини, що не належать множині V( ) V( ) V( ). Одержану послідовність позначимо z1, z2, ..., zs. Припустимо для визначеності, що z1V( ). Якщо z1=y1, то необхідно z2, z3,.., zs V( ). Отже, z1y1. Виберемо максимальний індекс t{1,2,...,s}, такий що ztV( ). Очевидно, що zt=y1 і z1, z2, ..., ztV( ). Припустимо для визначеності, що zt+1V( ). Тоді необхідно zt+1=y2 і zt+1 , ..., zs V( ). Одержано суперечність з умовою