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

V( ){z1, z2, ..., zs}.

Теорема 1. Скінченне дерево T(V,E) являється qhc-деревом, тоді і тільки тоді, коли існує такий шлях x0, x1, ...,xd, що всі вершини з множини V\ { x0, x1, ...,xd} є кінцевими вершинами дерева.

Доведення. Необхідність. Нехай d - діаметр дерева, тобто відстань між двома найбільш віддаленими його вершинами x0, xd. Позначимо через x0, x1, ...,xd найкоротший шлях від x0 до xd. Тоді

B(x0,1)={x0,x1}, B(xd,1)={xd-1, xd}

і кожна вершина з множин

B(x1,1)\{x0,x1,x2}, B(xd-1,1)\{xd-2,xd-1,xd}

є кінцевою. Візьмемо довільний індекс i{2,3,...,d-2}. Оскільки

B(xi-1,1) 3, B(xi+1,1)3,

то за лемою 5.1 кожна вершина з множини B(xi,1)\{xi-1,xi,xi+1} є кінцевою вершиною дерева.

Достатність. Для d=0 теорема очевидна: будь-яка нумерація множини V є qh-циклом. Припустимо, що d>0 і індукцією по d доведемо існування qh-циклу z0, z1,…, zn-1, такого що z0=x0, z1=x1. Можна вважати, що в умові теореми x0, xd-кінцеві вершини дерева. Для d=1 покладемо z0=x0, z1=x1. Нехай d>1 і B(x1,1)={x0,x1,x2,y1,y2,…ym}. Видалимо вершини x0,y1,y2,…ym і ребра {x0,x1}, {x1,y1}, {x1,y2},… {x1,ym}. Одержимо дерево T з шляхом x1,x2,…,xd, що задовольняє умову теореми. За припущенням індукції в T існує qh-цикл V1, V2, … Vs, такий що v1=x1, v2=x2 . Тоді

x1, x0, y1,y2,…ym, v2 ,v3, … vs -

qh-цикл в дереві T, що задовольняє індуктивному припущенню.

Задача 1. Довести, що дерево T є гамільтоновим графом тоді і тільки тоді, коли V(T)=1 або V(T)=2.

Задача 2. Нехай Gr(V1,E) - qhc-граф, |V|=n, r - дільник числа n. Довести, що існує врівноважене розбиття V0, V1,…, Vr-1 , таке що

dist(V0, V1) 2, dist(V1, V2) 2,…, dist(Vr-2, Vr-1) 2, dist(Vr-1, V1) 2 .

Нехай Gr(V,E) - скінченний зв'язний граф, |V|=n. Якщо |B(x,1)| +1 для будь-якої вершини xV, то за теоремою Дірака [5, стор. 74] граф Gr(V,E) є гамільтоновим. Ми доведемо достатню ознаку квазігамільтоновості графа, що є аналогом цієї теореми Дірака.

Теорема 5.2. Нехай Gr(V,E) - скінченний зв'язний граф, |V|=n. Якщо |B(x,2)| +1 для будь-якої вершини xV, то граф Gr(V,E) є квазігамільтоновим.Доведення. Серед послідовностей y1,y2,…,yk різних вершин графа з умовою d(y1,y2)2, d(y2,y3)2,…, d(yk-1,yk)2, виберемо послідовність x1,x2,…,xt максимальної довжини. Очевидно, що B(x1,2){x1,x2,…,xt}, B(xt,2){x1,x2, …, xt}. Оскільки tn і |B(x1,2)| +1, |B(xt,2)| +1, то знайдуться такі вершини xi,xi+1, i{1,2,…,t-1} що xi+1B(x1,2), xiB(xt,2). Перенумеруємо вершини x1,x2,…,xt в такому порядку

x1,xi+1,xi+2,…,xt,xi,xi-1,…,x2 .

Запишемо цю послідовність як z1,z2,…,zt і помітимо, що

d(z1,z2)2, d(z2,z3)2, …, d(zt-1,zt)2, d(zt,z1)2.

Припустимо, що t