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

Реферат на тему:

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

Однорідний граф Gr(V,E) скінченного степеня s називається калейдоскопічним, якщо існує розфарбування (: V({0,1,(,s}, таке що |((B(x,1))|=s+1 для будь-якого x(V. В цьому разі розфарбування ( теж називається калейдоскопічним. Отже, калейдоскопічні графи – це графи, що допускають калейдоскопічне розфарбування. Дамо рівносильне означення: розфарбування (: V({0,1,(,s} називається калейдоскопічним, якщо в кожній кулі одиничного радіуса немає двох однокольорових вершин.

З точки зору розкладності калейдоскопічні графи – це однорідні графи скінченого степеня, максимально розкладні відносно сім’ї всіх одиничних куль.

Розпочнемо дослідження калейдоскопічних графів з їх елементарних властивостей та прикладів. Далі запис a|b означає, що ціле число a є дільником цілого числа b.

Лема 1. Нехай Gr(V,E) – скінченний калейдоскопічний граф степеня s, (: V({0,1,(,s} – калейдоскопічне розфарбування. Тоді справедливі такі твердження:

s+1/n;

|(--1(0)|=|(--1(1)|=…=|(--1(s)|.

Доведення. Для кожного i({0,1,(,s} сім’я куль {B(x,1): x((--1(i)} утворює розбиття множини вершин V. Оскільки |B(x,1)((--1(i)|=1 , то

(s+1)|(--1(i)|=|V|.

З цієї рівності випливають обидва твердження леми.

Приклад 1. Нехай Grn(Vn,En) – циклічний граф з n>2 вершинами. Припустимо що Grn(Vn,En) калейдоскопічний. Оскільки Grn – однорідний граф степеня 2, то 3|n за лемою 3.1(і). З іншого боку, якщо 3/n, то періодичне 3-розфарбування множини Vn є калейдоскопічним.

Приклад 2. Розглянемо п’ять правильних многогранників у просторі як скінченні графи і покажемо, що серед них калейдоскопічними є лише тетраедр, куб та ікосаедр. Очевидно, що кожне 4-розфарбування множини вершин тетраедра є калейдоскопічним. Зафіксуємо довільну вершину x куба і довільне 4-розфарбування кулі B(x,1). Далі, кожну вершину y' куба, симетричну до деякої вершини y(B(x,1) відносно центра куба пофарбуємо кольором вершини y. Одержимо калейдоскопічне розфарбування куба. Аналогічне розфарбування виявляється калейдоскопічним і для ікосаедра. Оскільки октаедр має 6 вершин і є однорідним степеня 4, то він не є калейдоскопічним за лемою 3.1(і). Нарешті, додекаедр є однорідним графом степеня 3. Візьмемо довільний п’ятикутник, що є гранню додекаедра. Для будь-якого 4-розфарбування множини вершин додекаедра, знайдуться принаймні дві однокольорові точки на вказаній грані. Отже, одинична куля з центром в деякій вершині грані містить дві однокольорові вершини.

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

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

(s+1)|X|=2m;

s+1=p+q, p>q;

якщо x(V(i), i({0,1}, то |B(x,1)(V(i)|=p, |B(x,1)((V\V(i)|=q.

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

Доведення. Позначимо k0=|X(V(0)|, k1=|X(V(1)|. З умов (і), (іv) випливають такі нерівності

pk0+qk1 ( m,

qk0+pk1 ( m.

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

px0+qx1 = m,

qx0+px1 = m.

.

Лема 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 для яких виконуються умови:

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

(s+1)|X|=nm;

s+1=p+2q, p>2q;