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

Загальну проблему 1 характеризації квазігамільтонових графів можна послабити до серії проблем про достатні ознаки квазігамільтоновості. Ось лише дві з них.

Проблема 3. Чи кожен ейлерів граф є квазігамільтоновим? Нагадаємо, що звязний граф називається ейлеревим, якщо локальний степінь кожної його вершини є парним числом.

Проблема 4. Чи кожен планарний граф є квазігамільтоновим?

Вершину x qhc-графа Gr(V,E) назвемо особливою, якщо існує qh-цикл x1,x2,…,xn в Gr, такий що x=x1 і d(x1,x2)=1. Якщо V={x}, то також вважаємо вершину x особливою. З доведення достатності в теоремі 5.1 випливає, що кожне qhc-дерево має особливу вершину. Для конструктивного описання qhp-дерев введемо дві операції приєднання.

Операція А. Нехай Gr1(V1,E1) - qhp-граф з qh-шляхом y1,y2,…ym. Візьмемо довільний qhc-граф Gr2(V2,E2), V1V2 з особливою вершиною x і qh-циклом x=x1,x2,…,xn, d(x1,x2)=1. Побудуємо новий граф Gr(V1V2,E), де E=E1E2{(ym,x1)}. Зауважимо, що послідовність вершин

y1, y2, …, ym, x2, x1, xn, xn-1, … , x3

є qh-шляхом в графі Gr. Отже, в результаті операції приєднання А отримано новий qhp-граф Gr. Крім того, якщо Gr1, Gr2-дерева, то Gr - теж дерево.

Операція В. Нехай Gr(V,E) - qhp-граф з qh-шляхом y1,y2,…ym. Візьмемо довільну вершину yt, таку що d(y1,yt)=1. Виберемо довільний елемент xV і розглянемо граф Gr(V{x},E), де E=E{(x,yt)}. Відмітимо, що послідовність

x, y1, y2,…, yt, yt+1 , …, ym

є qh-шляхом в графі Gr. Отже, в результаті операції приєднання В отримано новий qhp-граф Gr. Крім того, якщо граф Gr був деревом, то Gr теж дерево.

Теорема 3. Скінченне дерево T(V,E) являється qhp-графом тоді і тільки тоді, коли T(V,E) є qhc-деревом, або T(V,E) можна отримати з деякого qhc-дерева послідовним застосуванням операцій А, В приєднання qhc-дерев.

Доведення. Достатність випливає з означення операцій приєднання А і В. Для доведення необхідності зафіксуємо деякий qh-шлях y1,y2,…,ym в дереві T(V,E) і розглянемо два випадки.

Випадок 1: Вершина y1 не є кінцевою вершиною дерева T(V,E). Виберемо максимальний індекс t{1,2,…,m}, такий що d(y1,yt)=1. Позначимо через дерева з коренями y1, yt, одержані видаленням з дерева T(V,E) ребра {y1,yt}. Якщо t=m, то T(V,E) - qhc-граф. Припустимо, що t
Випадок 2: Вершина y1 є кінцевою вершиною дерева T(V,E). Виберемо індекс t{1,2,…,m} так, що (y1,yt)E. Позначимо через дерево з коренем yt, одержане видаленням з T(V,E) ребра (y1,yt). Ясно, що V( )={y2, y3,…, yt,…, ym} і - qhp-граф з qh-шляхом y2, y3,…, yt, yt+1 ,…, ym. Якщо t=2, то T(V,E) можна отримати з за допомогою операції А. Якщо ж t >2, то T(V,E) можна отримати з за допомогою операції В.

Нагадаємо, що нескінченний зв'язний граф Gr(V,E) називається qr-графом, якщо існує бієкція f:V, така що d(f(i),f(i+1))3 для будь-якого i.

Зв'язний граф називається локально скінченним, якщо локальний степінь кожної його вершини скінченний.

Стовбуром нескінченного дерева T(V,E) називається ін'єктивна послідовність {xn:n} його вершин, що задовольняє такі умови

(і) d(xn, xn+1)=1 для всіх n;

(іі) після видалення вершин {xn:n} дерево T(V,E) розпадається на скінченні дерева.