Розкладність графів. Калейдоскопічні графи

Приклад 3. Нехай

G= , m , m>2, S={a,b,b-1,e}.З геометричної точки зору граф Cay(G,S) є призмою з 2m вершинами. Припустимо, що граф Cay(G,S) калейдоскопічний і покажемо, що 4|m. Згодом (приклад 3.6) ми доведемо і обернене твердження.

Для того, щоб застосувати лему 3.2 покладемо s=3, p=3, q=1, V=G, ={0,1}, V(0)={(0,x): x}, V(1)={(1,x): x}. Зафіксуємо калейдоскопічне розфарбування : V{0,1,2,3} і позначимо Xi= -1(i), i{0,1,2,3}.За лемою 3.2, |Xi V(0)|= |Xi V(1)| для всіх i{0,1,2,3}. За лемою 3.1(іі), |Xi|= . Оскільки V(0)= (X0 V(0)) (X1 V(0)) (X2 V(0)) (X3 V(0)) , то 4|m.

Приклад 4. Нехай

G= , n, m , n, m>2, S={a, a-1, b, b-1,e}.

Припустимо, що граф Cay(G,S) калейдоскопічний і покажемо, що 5|m, 5|n.

Для того, щоб застосувати лему 3.3 покладемо

s=4, p=3, q=1, V=G, ={0,1,n-1}, V(i)={(i,x): x}, i{0,1,…,n-1}. Зафіксуємо калейдоскопічне розфарбування : V{0,1,2,3,4} і позначимо Xj= -1 (j), j{0,1,2,3,4}. З леми 3.3 випливає

|Xj V(0)|=|Xj V(1)|=|Xj V(n-1)|, j{0,1,2,3,4}.

За лемою 3.1(іі), |Xj , j{0,1,2,3,4}. Оскільки V(0)= , то 5|m. Аналогічно доводиться, що 6|n.

Перший метод побудови калейдоскопічних графів базується на такому означенні.

Розглянемо групу G з одиницею e. Нехай X, Y G. За означенням (X,Y) називається калейдоскопічною парою, якщо множина X скінченна і виконуються такі умови

(i)eX, X=X-1, G=;

(ii)eY, G=XY;

(iii)x-1XXx YY-1=e для всіх xX.

SS={e,a,a-1,b,b-1, a2,b2, a-2, b-2, ab, a-1b-1 , a-1b, ab-1}

і покладемо H=. Безпосередня перевірка дає SH=G, SSH={e}.

Зауважимо, що цей граф можна розглядати як квадратну мозаїку на площині. Аналогічно визначаються калейдоскопічні розфарбування для трикутних і шестикутних мозаїк на площині.

Викладемо другий метод побудови калейдоскопічних графів на основі графів Келі Cay(G,S) груп при деяких обмеженнях на множину твірних S.

Крок 1. Нехай G - група з одиницею e, S - скінченна підмножина групи, G=, eS, S=S-1. Припустимо також, що |S|=r(r-1) для деякого натурального числа r>1 і S не містить елементів порядку 2. Побудуємо розбиття S=S1S2Sr, таке що |Si|=r-1, i{1,2,…,r} i |Si-1 Sj|=1 для всіх різних індексів i,j{1,2,…,r}. Для цього розіб'ємо множину S=AB так, що B=A-1. Таке розбиття можливе, оскільки S не містить елементів порядку 2. Виберемо довільні елементи x1,x2,xr-1A і покладемо S1={x1,x2,…,xr-1}. Віднесемо елементи x1-1,x2-1, xr-1-1 до майбутніх підмножин S2, S3, Sr.Виберемо довільні елементи y2, y3, yr-1 A\{x1,x2,…,xr-1}. Покладемо S2={x1-1,y2,y3,yr-1} і віднесемо елементи y2-1, y3-1, yr-1-1 до майбутніх підмножин S3, S4…, Sr. Виберемо довільні елементи

z3, z4, zr-1 A\{x1,x2 xr-1, y2, y3, yr-1 },