ПРИКЛАДНАЯ МАТЕМАТИКА

УДК 519.1

Р. Р. Камалян, П. А. Петросян

О равновесных реберных раскрасках регулярных графов

(Представлено академиком Ю.Г. Шукуряном 16/II 2005)

   В работе рассматриваются неориентированные графы без кратных ребер и петель. Не определяемые в работе понятия и обозначения можно найти в [1-3].
   Множество вершин графа G обозначается через V(G), множество ребер - E(G), максимальная из степеней вершин G - D(G), хроматический класс - (G). Для вершины v О V(G) определим множество J(v) Н V(G) следующим образом: J(v) = { u О V(G)|(u,v) О E(G)}.
   Функция f:E(G)® N называется правильной реберной раскраской графа G, если для любых двух смежных ребер e1 О E(G) и e2 О E(G) f(e1) f(e2).
   Правильную реберную раскраску f графа G назовем равновесной t-раскраской, если для каждого i, 1 Ј i Ј t, существует хотя бы одно ребро ei О E(G), для которого f(ei) = i, и для любых двух вершин v1 О V(G), v2 О V(G)

   Для t і 1 через ( m)t обозначим множество всех графов, для которых существует равновесная t-раскраска. Обозначим: ( m) є ( m)t. Для графа G О ( m) обозначим через w(G) и W(G), соответственно, наименьшее и наибольшее значение t , при котором G О ( m)t.
   Ясно, что для G О ( m) w(G) і D(G), W(G) Ј |E(G)|. Отсюда и из теоремы Турана [1] следует
   Утверждение 1. Если G О ( m) и G не имеет треугольников, то W(G) Ј Ј ë[(|V(G)|2)/4] û.
   Лемма. Если G регулярный граф и (G) = D(G), то G О ( m) и w(G) = D(G).
   Доказательство. Рассмотрим правильную реберную раскраску f графа G в цвета 1,2,ј,D(G). Так как G регулярный граф, то f является равновесной D(G) - раскраской. Отсюда вытекает, что G О (m) и w(G) Ј D(G).
   Лемма доказана.
   Следствие 1. При   n і 2  C2n О ( m),  w(C2n) = W(C2n) = 2.
   Следствие 2. При  n і 1   K2n О ( m),  w(K2n) = 2n - 1.
   Следствие 3. При  n і 1   Qn О ( m),  w(Qn) = n
   Среди регулярных графов G с (G) = D(G) + 1 существуют графы, удовлетворяющие условию G О (m), и существуют графы, удовлетворяющие условию G П ( m).
   Утверждение 2. При  n і 2   C2n+1 П ( m).
   Утверждение 3. Если  G  есть  граф  Петерсена [1],  то   G О ( m).
   Доказательство. Пусть V(G) = {x1,x2,x3,x4,x5,y1,y2,y3,y4,y5}, E(G) = {(x1,x2), (x2,x3), (x3,x4), (x4,x5), (x5,x1), (y1,y3), (y3,y5), (y5,y2), (y2,y4), (y4,y1), (x1,y1), (x2,y2), (x3,y3), (x4,y4), (x5,y5)}. Определим раскраску f ребер графа G следующим образом:
f((x1,x2)) = 7, f((x2,x3)) = 2, f((x3,x4)) = 3, f((x4,x5)) = 6, f((x5,x1)) = 1,
f((y1,y3)) = 3, f((y3,y5)) = 2, f((y5,y2)) = 5, f((y2,y4)) = 4, f((y4,y1)) = 5,
f((x1,y1)) = 2, f((x2,y2)) = 1, f((x3,y3)) = 5, f((x4,y4)) = 1, f((x5,y5)) = 3.
   Нетрудно убедиться, что f является равновесной 7-раскраской ребер графа G.
   Утверждение 3 доказано.
   Теорема 1. При  n і 1
          1. Kn,n О ( m);

          2. w(Kn,n) = n;
          3. W(Kn,n) =

   Доказательство. Так как Kn,n при любом n О N является регулярным графом, удовлетворяющим
равенству (Kn,n) = D(Kn,n) = n, то из леммы вытекают утверждения 1 и 2 доказываемой теоремы.
   Утверждение 3 доказываемой теоремы при n Ј 2 очевидно. Докажем, что оно верно при n і 3.
Заметим, что каждому магическому [2] квадрату порядка n можно сопоставить равновесную n2-
раскраску ребер графа Kn,n. Так как для любого n і 3 существует [2] магический квадрат порядка
n, то при n і 3 W(Kn,n) і n2 = |E(Kn,n)|.
   Теорема 1 доказана.
   Следствие 4. Для  графов  Kn,n  при  n і 3  оценка  утверждения 1 достижима.
   Теорема 2. При  m і 2   W(K4m) і W(K2m) + 4m2.
   Доказательство. Пусть V(K4m) = {x1,x2,ј,x4m}.
   Пусть G1 есть подграф графа K4m, порожденный вершинами x1,x2,ј,x2m. Ясно, что G1
изоморфен графу K2m и, следовательно, ввиду следствия 2, существует равновесная W(K2m)-
раскраска f1 ребер графа G1.
   Пусть G2 есть подграф графа K4m, порожденный вершинами x2m+1,x2m+2,ј,x4m.
   Определим подграф G3 графа K4m следующим образом:

V(G3) є V(K4m);    E(G3) є E(K4m)\(E(G1)ИE(G2)).

   Легко видеть, что G3 изоморфен полному двудольному графу K2m,2m и, следовательно, ввиду
теоремы 1, G3 О ( m). Пусть f2 есть равновесная 4m2-раскраска ребер графа G3.
   Определим раскраску F ребер графа K4m.
   Для i = 1,2,ј,4m и j = 1,2,ј,4m при i j положим:

F((xi,xj)) = м
п
н
п
о
f1((xi,xj)),
если
1 Ј i Ј 2m,
1 Ј j Ј 2m;
f1((xi-2m,xj-2m)),
если
2m + 1 Ј i Ј 4m,
2m + 1 Ј j Ј 4m;
f2((xi,xj)) + W(K2m),
если
1 Ј i Ј 2m,
2m + 1 Ј j Ј 4m.
   Легко видеть, что F является равновесной (4m2 + W(K2m))-раскраской ребер графа K4m.
   Теорема 2 доказана.
   Следствие 5. При m і 2  
і [(22m - 7)/3].

   Доказательство. По теореме 2
W(K2m) і W(K2m-1) + 22(m-1)
W(K2m-1) і W(K2m-2) + 22(m-2)
.................................................
W(K8) і W(K4) + 22·2.

Складывая эти неравенства, получим:
   Следствие 5 доказано.
   Следствие 6. При  m і 2   W(K4m) і 4m2 + 2m - 1.
   Утверждение 4. Для p і 2 существует граф G О ( m), для которого W(G) і |V(G)| + p.
   Доказательство. По данному p і 2 выберем m, удовлетворяющее неравенству 4m2 - 2m - 1 і p.
Положим G є K4m. По следствию 6 W(G) і 4m2 + 2m - 1 = 4m2 - 2m - 1 + |V(G)| і |V(G)| + p.
   Утверждение 4 доказано.
   Утверждение 5. Для  p і 3  существует  граф   G О ( m),  для  которого W(G) - w(G) і p.
   Доказательство. По данному p і 3 выберем m, удовлетворяющее неравенству 4m2 - 2m і p.
Положим G є K4m. Из следствий 2 и 6 получим: W(G) і 4m2 + 2m - 1 = 4m2 - 2m + 4m - 1 і p + w(G).
   Утверждение 5 доказано.
   Настоящее исследование поддержано целевой программой 04-10- 31 РА.

     Институт проблем информатики и автоматизации НАН РА

Литература

     1. Harary F.  Graph Theory. Addison-Wesley. Reading. MA. 1969.
     2. Постников М.М.  Магические квадраты. М. Наука. 1964.
     3. Визинг В.Г.  Хроматический класс мультиграфа. Кибернетика. 1965. N3. С. 29-39.