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

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

px0+qx1 = m,

qx0+px1 = m.

Оскільки p>q, ця система має єдиний розв’язок. З іншого боку, система має очевидний розв’язок x0=x1= .

Лема 3. Нехай Gr(V,E) – скінченний однорідний граф степеня s, |V|=nm, m, n – натуральні числа 2, XV. Припустимо, що існують розбиття V=V(0) V(1) V(n-1), |V(0)|=|V(1)|=…=|V(n-1)|=m і натуральні числа p, q для яких виконуються умови:

(i) {B(x,1): xX} =V;

(ii)(s+1)|X|=nm;

(iii)s+1=p+2q, p>2q;

(iv)якщо 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}. Отже, ця система має єдиний розв’язок.. З іншого боку, система має очевидний розв’язок

x0=x1=…=xn-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.