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

якщо x(V(i), i({0,1,..,n-1}, то

B(x,1)( V((i-1) mod n)( V(i mod n)( V((i+1) mod n),

|B(x,1)( V(i mod n)|=p,

|B(x,1)( V((i-1) mod n)|= |B(x,1)( V((i+1) mod n)|=q.

Тоді |X( V(0)|=|X( V(1)|=…=|X( V(n-1)|.

Доведення. Позначимо ki=|X( V(i)|, i({0,1,…,n-1}. З умов (і), (іv) випливають такі нерівності

pk0+qkn-1+qk1( m,

pk1+qk0+qk2( m,

……………………..

pkn-2+qkn-3+qkn-1( m,

pkn-1+qkn-2+qk0( m.

Додамо всі ці нерівності і отримаємо p|X|+2q|X|( nm . З умов (іі), (ііі) випливає, що (p+2q)|X|=nm. Звідси випливає, що числа k0, k1,…, kn-1 задовольняють систему лінійних рівнянь

.

Помітимо, що визначник ( матриці системи є циркулянтом. Отже (=f((0) f((1)…f((n-1), де (0 , (1,…, (n-1 - комплексні корені рівняння zn=1, f(x)=p+qx+qxn-1. Оскільки p>2q, то f((i)( 0 для всіх i({0,1,…,n-1}. Отже, ця система має єдиний розв’язок.. З іншого боку, система має очевидний розв’язок

.

Нагадаємо означення неорієнтованого графа Келі групи. Для довільної непорожньої підмножини А групи G позначимо через найменшу підгрупу групи G, що містить A. Нехай G – група з одиницею e, S(G, S=S-1 і G=. Графом Келі Cay(G,S) групи G, визначеним системою твірних S називається граф з множиною вершин G і множиною ребер E, де x,y(E тоді і тільки тоді, коли x( y і x-1y(S. Якщо множина S скінченна e(S і |S|-1=s, то Cay(G,S) - однорідний граф степеня s.

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

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

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

. Оскільки 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}.

, то 5|m. Аналогічно доводиться, що 6|n.

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

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

e(X, X=X-1, G=;