О структуре интервальных раскрасок полных двудольных графов

Р.Р. Камалян

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

Доказано, что при т = Хп, где X є N , любая интервальная раскраска полного двудольного графа Кт п состоит из интервальных

раскрасок его реберно непересекающихся подграфов О^…,Ох, каждый из которых изоморфен графу Кп п.

Ключевые слова: полный двудольный граф, интервальная раскраска, структура.

Введение: определения, обозначения, цель работы

В работе рассматриваются неориентированные связные графы без кратных ребер и петель [1]. Не определяемые понятия и обозначения можно найти в [2]. Множество вершин графа О обозначаем через У(О), множество ребер через Е(О), наибольшую из степеней вершин через А(О), хроматический класс [1] через х (О). Множество всех правильных реберных г — раскрасок графа О, где х'(О) < г <| Е(О) |, обозначим через а(О,1), и пусть

|Е(О)|

а(О) = ^ а(О,1). Если с є а(О), х є У(О), то множество

1=Х'(О)

{с(е)/е єЕ(О), е инцидентно х} обозначим через Ба(х,с).

Если О непустое конечное подмножество множества N , то через 1(0) и Ь(О) обозначаем наименьший и наибольший элемент О , соответственно. Непустое конечное подмножество О множества N назовем интервалом, если из 1(0) < г < Ь(В), г є N следует г є О . Интервал О назовем И — интервалом, если |О|= И. Интервал О обозначим через Іпі;^,И), если 1(О) = q, |О|= И. Непустое конечное подмножество О множества N назовем разрывным, если

О         не является интервалом, а число 1 назовем разрывом О , если

О структуре интервальных раскрасок полных двудольных графов

подпись: 481(0) < 1 < МР), 1 є N, 1 £ Р . Множество разрывов разрывного множества Р обозначим через ГЯ2(Р) .

Скажем, что правильная реберная раскраска с є а(О) интервальна в вершине х0 є У(О) графа О, если Ба(х0,с) является интервалом; скажем, что с является интервальной раскраской графа О, если для Ух є У(О) с интервальна в х. Интервальные раскраски графов были введены в [3], интерес к ним связан с тем, что в случае двудольных графов они могут служить графовыми моделями “безоконных” учебных расписаний. В [4] было доказано, что для любых т, п є N полный двудольный граф Кт п имеет интервальную раскраску в цвета

1,2,…,1 тогда и только тогда, когда т + п-а(т,п) < Ї < т + п — 1, где а(т,п) есть наибольший общий делитель т и п . Целью настоящей работы является исследование структуры интервальных раскрасок графов Кт п при т, кратном

п (отметим, что при о(т, п) = 1 структура интервальных раскрасок графов Ктп исследована в [5,6]).

Множество У(Ктп) вершин графа Ктп считаем представленным в виде X и У, где X = {х1,…,хп} одна доля графа, а У = {у1,…,ут} другая. Всюду в настоящей работе предполагаем, что п,X є N, п > 2, т = Хп, и для Т = 1,…,X используем обозначение Ут = {у1+(т—1)п,…,утп}.

Для X’ е X, У» е У в случае X’ ^ 0, У’ ^ 0 через Т(Х’, У’) будем обозначать подграф графа Кт п, порожденный подмножеством X’ и У’ его вершин, а через (X’, У’) множество ребер графа Т^’, У’) . Цвет ребра (х, у) при раскраске с єа(Ктп) обозначаем через с((х,у)). Для ие (X,У),

сєа(Ктп) в случае И^0 положим С(И) = ^ {с((х,у))}.

(х,у )єИ

Для і є ІШ(1, п) определим множество Я(і) = {І є N І = і(то<іп)}; если а є Я(і), будем писать также, что г(а) = і. Если с єа(Ктп), то для і = 1,…,п и т = 1,…,X положим Б((і,т),с) = {І є ІШ(1,п)/| С(({хі},Ут)) пЯ(І) |> 2}, а для

п

т = 1,…, X       обозначаем     Н(т,с) = ^ Б((і, т),с),   и          пусть

і=1

0(с) = {т/ 1 <т<Х, Н(т,с) ^0}. Для с єа(Ктп), Р е N, И е ^,У) положим {(Р, И, с) =| {(х, у)І(х, у) є И, с((х, у)) є Р}|.

При употреблении обозначений в тех случаях, когда ясно, о какой раскраске речь будем использовать сокращенные обозначения, опуская символ названия раскраски. Так, например, будем писать Г(Р, И) вместо Г(Р, И, с) и т.п.

Результаты

Сначала отметим, что имеет место следующая, простая

Лемма 1. Пусть В разрывное множество, |в| = п , В с 1п1;(а, 2п — 1) . Если |ВпЯ(1)| = 1 при 1 = 1,…,п, то существует такое 1 > а + п — 1, что

е га2(В).

Лемма 2. Пусть с интервальная раскраска графа Кт п, такая, что для т = 1,…,X С(({х1},Ут)) = Ы((т1)п + 1,п) . Тогда для т = 1,…,X :

тп е С((Х, {У]})), ] = (т1)п +1,…, тп;

Щтп}, (X, У)) = Щтп}, (X, Ут)) = п;

С((Х, Ут)) с 1п1((т 1)п +1,2п — 1);

тп        е С(({х!},ут)), 1 = 1,…,п;

^0,       (Х,УТ)) = п, ] = 1,…,п.

Доказательство. Сначала отметим, что утверждение 5) следует из интервальности раскраски с и равенств |Ут | = п, т = 1,…, X .

Так как для ] = 1,…,п 1 < c((x1,yJ)) < п и С((Х,{у^)) п-интервал, то

п е С((Х,{У]})),] = 1,.,п         С1)

следовательно, Щп}, (Х, У1)) = п. Поскольку |Х| = |У11 = п, то отсюда и из условия леммы следует, что для 1 = 1,…,п п е С(({х1}, У1)). Так как для ] = 1,…,п С((Х,{у]})) п-интервал, то из (1) следует, что для 1 = 1,…,п, ] = 1,…,п 1 < с((х1,У])) < 2п — 1 . Этим лемма для т = 1 доказана.

Пусть лемма доказана для т = 1,…, 8 . Если 8 = Х , то этим ее доказательство завершено. Поэтому предположим, что 8 <Х .

Так как 8п е С(({х1},У8)) для 1 = 1,…,п, то

8п £ С((Х,{У]})), ] = 8п +1,…,(8 + 1)п         (2)

Из условия леммы имеем

8п + 1 < с((х;, У])) < (8 + 1)п , ] = 8п + 1,…,(8 + 1)п           (3)

Из (2) и (3) следует, что при 1 < а <8п

а е С((Х,{У]})), ] = 8п +1,…,(8 + 1)п            (4)

Из (3) и (4), с учетом того, что С((Х,{у]})) для ] = 8п +1,…,(8 + 1)п пинтервал, получаем

(є + 1)п єС((Х,{у^)), І = 8й + 1,…,(є + 1)п   (5)

следовательно, Г({(є +1)п}, (X, Уе+1)) = п . Поскольку |Х| = (У^) = п , то отсюда и из условия леммы следует, что для і = 1,…,п (є + 1)п є С(({хі},Ує+1)) . Так как для ] = вп + 1,…,(в + 1)п С((Х,{у^})) п-интервал, то из (5) следует, что для

і           = 1,…,п, І = вп + 1,…,(в + 1)п вп +1 < е((хі,у^)) < (в + 1)п + п-1.

Лемма 2 доказана.

Лемма 3. Пусть с єа(Ктп) такова, что для і = 1,…,п С(({хі},У)) является интервалом, для ] = 1,…,п, т = 1,…, X Г(Я(І), (Х,Ут), с) = п, для т = 1,…,X С((Х,УТ))^ 1п1;((т1)п + 1,2п-1). Тогда если 0(с) Ф0, то 1(0(с)) = 1.

Доказательство от противного. Пусть

1(0(с)) = Т0 Ф 1          (6)

Отсюда и из условия леммы следует, что 1 <т0 < X. По определению, Н(т0) Ф 0. Пусть

1(Н(т0)) = jo, 1 < Іо < п         (7)

и І0 є Е((і0, т0)) , 1 < і0 < п . По определению,

С(({Хі0},УТ0)) пЯ(І0^ > 2   (8)

Из условия леммы получаем |С(({х^ }, УТо)) п ^0) <

|С((Х, УТ0)) п яа) < |іп1((І0 1)п +1,2п — 1) п яа) < 2.

Отсюда и из (8) следует |С(({х^ }, УТо)) п я(І0^ = 2. пусть

С(({хю},УТ0)) п Я(І0) = {і’,П          (9)

Предположим, для определенности, что

г "< г" (10)

Из соотношений (9), (10) и условия леммы следует

(т0 1)п+1 < г" < т0п < г"+п = г" < т0п + п — 1          (11)

Поскольку Я(І’)пЯ(І») = 0 при І’ Ф І», 1 < І’ < п,1 < І»< п, и

С(({хіо(,У,0)) с           то

І=1

п = |С(({х,.},У,.)) = и(С(({х,.},У,.))пК(])> =Е|С(({х1.},У,.))пВД .

]=1       Н

Отсюда и из (8) следует, что существует ], 1 < ] < п, ] Ф ], такое, что С(({х1о},УТо)) п Яа) = 0         (12)

Очевидно, существует единственное р0, 0 < р0 < п — 1, такое, что (1 + Ро) е МО» п Я^) . Отсюда и из (12) получаем

(1 " + Ро) е С(({х10},Ух0»    (13)

Из условия леммы следует, что

Г(Я(п),(Х,УТ0)) = п   (14)

Ясно, что 1п1((т0 1)п + 1,2п — 1) п Я(п) = {т0п} . Отсюда, из (14) и условия леммы следует Щт0п},(Х, У)) = п , откуда, ввиду правильности раскраски с , получаем

т0п е ад^ЛтД1 = 1, . ,п          (15)

Из (9) и (13) следует р0 > 0, а из (13) и (15) получаем 1 " + р0 Ф т0п .

Случай 1 1 " + Р0 <т0п.

Из (11) получаем

(т0 1)п +1 < 1 " < 1 " + р0 < т0п < 1 " + п = 1" < т0п + п -1           (16)

Случай 1а). 1(С(({х10 }, У))) < 1 "(т0 1)п .

Пусть Б = 1п1(1(С(({х10},У))), т0п1(С(({х10},У))) +1)пЯ(]1). Легко видеть, что из (16) и условия случая 1а) следует

И = т0 (17)

Так как С(({х^},У)) интервал и т0п е С(({х^},У)), то Б с С(({х^},У)). Отсюда и из условия леммы следует, что

Б с С(({х10}, У Ут)) и, ввиду (12), Б с С(({х10}, У Ут)) . Отсюда и из очевидт=1        т=1

Х0 — 1   Х0 — 1

ного    равенства       С(({х^}, и у,))=и с(((х1.},у,))            следует

т=1      т=1

т0

Б с и С(({х^},Ут)), откуда, с учетом (17), получаем, что существует

С(((х1о},УТ1))пЯ(]1> > 2, следовательно,

е Т1)) , н(т1) Ф 0, Т1 е 0(с), что противоречит (6), поскольку

подпись: т1,1 < т1 < т0 - 1, такое, чтоСлучай 1б). l(c(({xi0}, Y))) > X'(то 1)п .

Из (9) следует (X’ (т0 1)п) е Я(]0). Отсюда и из условия случая 1б) следует

1(С(({х^ },У)) пяа)) > X’ (Т0 2)п      (18)

Т0

Из (9), (16) и условия леммы получаем Ь(С(({х^}, и у,)) п Я(]0)) = X".

подпись: отсюда, из (9) и (18)подпись: <т0. из этого неравенства, праС(({х,|, ик)) п R(j„)

подпись: c(({xi.|, и)у,)) п r(j„)вильности раскраски с и (8) получаем: т0 >

Т=1

подпись: и^(с(({х,0}, уг)) п r(j„))То -1 .

подпись: >С(({х },У ))пЯ0„) + £ С(({х10},Уг))пЯ0„)

Т=1

подпись: - 2.>2 + £|С(({х },У,))пR(jо) , откуда £|С(({х10},У,))пЯ0„)

подпись: т=1Т=1

Следовательно,         существует     т2,1 <Т2 <Т0 — 1,         такое,  что

С(({Хю},УТ2)) п R(j0) = 0. Теперь из правильности раскраски с вытекает, что существует j2,1 < j2 < п, j2 Ф j0, для которого выполняется неравенство

С(({Х10},УТ2)) п > 2. 0тсюда следует, что Ь е Т2 )) , н(т2) Ф0 , т2 е 0(с) , что противоречит (6), поскольку Т2 — 1.

Случай 2. х’ + Ро >топ.

Поскольку р0 < п — 1, то из (11) следует:

(т0 1)п +1 < X’ < т0п < X’ + р0 < X’ + п = X’ < т0п + п — 1 (19)

Из условия леммы, правильности раскраски с и (12) имеем: п = Г(КЦ),(Х, У%)) = |С(({х1>},У1>)) п R(j1)| +

подпись: i=1 1ф1о подпись: i=1
1ф1о

+]С|С(({х1},У,,)) п R(jl )| = ]С|С(({х1},У,,)) п R(jl)

следовательно, существует ij,1 < ij < n , ij Ф i0, такое, что C(({xli},YTo)) n> 2. Поэтому jj e F((il, To)) и

ji e H(To)         (20)

Из (19) и определения числа p0 следует

r(t’ + Po) = ji = t’ + Po-Ton     (21)

Аналогично, из (io) и (19) следует

r(t") = jo = t’ + n — Ton (22)

Так как po < n , то из (21) и (22) вытекает неравенство j1 < ^ которое невозможно ввиду (7) и (2o).

Лемма 3 доказана.

Лемма 4. Пусть cea(Kmn) такова, что для i = 1,…,n C(({xi},Y)) интервал, для j = 1,…,n, t = 1,…, X f(R(j),(X,YT), c) = n, для t = 1,…, X C((X, YT)) e Int((T 1)n + 1,2n -1). Тогда Q(c) = 0 .

Доказательство от противного. Пусть Q(c) ^ 0 . По лемме 3, l(Q(c)) = 1. По определению, H(1) ^0 . В остальной части рассуждение ведется аналогично рассуждению, которое проводится для доказательства леммы 3 после установления неравенства H(to ) ^ 0 .

Лемма 4 доказана.

Лемма 5. Пусть X>2, и cea(Kmn) такова, что для i = 1,…,n C(({xi},Y)) интервал, для j = 1,…,n, т = 1,…,X f(R(j),(X,YT),c) = n, и для t = 1,…,X C((X, YT)) e Int((T 1)n + 1,2n — 1).

X-1

Тогда для i = 1,…,n: 1)C(({xi},YX)) интервал; 2)C(({xi}, ^ YT)) интерT=1

вал; 3)L(C(({xi|,l)y,))) + 1 = l(C(({xi(,Yx))); 4)1(C(({xi},UYt))) +

T=1      T=1

+m n = l(C(({xi},Yx ))).

Доказательство.

Предположим противное: существует такое io,1 < io < n, что C(({x^},YX)) разрывное множество. Из правильности раскраски c следует

|C(({xi,},Yx))| = n       (23)

По условию,

С(({х1о },У)) с 1)п + 1,2п — 1)           (24)

СлУчай а). При ] = 1,…,п С(({х1о},Уя))пЯ0 =1.

Поскольку С(({х^}, Ух)) разрывное множество, то из (23), (24) и леммы 1 следует, что существует такое 1, что

1 >^п   (25)

и

1 е гаг(С(({х1о},Уя)))           (26)

Так как С(({х^ }, Уя)) с С(({х^ }, У)) и С(({х^ }, У)) интервал, то из (26)

Я.-1

следует 1 е С(({х1 }, 0 Ут)) . Поэтому существует такое V 1 < то < ^-1, что

Т=1

1 е С(({х^},УТо)). Отсюда, по условию леммы, следует неравенство 1 < т0п + п — 1 < (^1)п + п — 1 = ^п — 1, противоречащее (25).

Случай б). Существует такое ]о,1 < ]о < п, что

|С(({х.},у)) пЯ(]о) * 1            (27)

Из правильности раскраски с следует

подпись: п =С(({хю),У1 ))| = |С(({х,,},У1)) п Я(]о) + 1|С(«х,},у)) п *(й|.

Н

.1* Jо

откуда, ввиду (27), ясно, что существует   ^ < п, для которого

С(({х^},Уя))пЯ^) > 2. Следовательно, Р((10,^)) *0, Н(^) *0 ,

0(с) * 0 , что противоречит лемме 4.

Этим утверждение 1) доказано.

Очевидно, для 1 = 1,…, п

С((К}, Оу)) п С(({х1},У)) = 0,С(({х1}, Цу )) и С(({х1},У)) = С(({х^,У)).

Т=1      Т=1

Отсюда, из условия леммы и доказанного утверждения 1) следует утверждение 2).

Утверждение 3) следует из условия леммы и доказанных утверждений

и 2).

Утверждение 4) непосредственно следует из утверждения 3), поскольку

А.-1

С(({х1} ,0Ут)) для 1 = 1,…,п является (т — п)-интервалом.

Т=1

Лемма 5 доказана.

Из леммы 5 следует

Утверждение 1. Пусть с є a(Kmn) такова, что для i = C(({xi},Y)) интервал, для j = 1,…,n, т = 1,…,X f(R(j),(X,YT),с) = n, и для т = 1,…,X C((X,YT))^ Int((T1)n + 1,2n-1). Тогда: 1)C(({xi},YT)) интервал, i = 1,…,n, т = 1,…, X; 2) если X > 2, то при i = 1,…,n, т = 1,…, X-1 l(C(({Xi},YT))) + n = l(C(({Xi},YT+1))).

Из утверждения 1 и леммы 2 вытекает

Теорема 1. Пусть интервальная раскраска с графа Kmn такова, что для т = 1,…, X C(({Xj},YT)) = Int((x1)n + 1,n). Тогда: 1)C(({xi},YT)) интервал, i = 1,…,n, т = 1,…,X; 2) подграф T(X,YT) графа Kmn интервально окрашен, C((X,YT)) ^ Int((x1)n + 1,2n -1), t = 1,…,X ; 3) если X > 2, то при i = 1,…,n, t = 1,…, X-1 1(C(({xi},Yt ))) + n = l(C(({Xi},YTfl))).

Более сложными рассуждениями можно показать [5], что теорема 1 допускает обобщение и на случай произвольных натуральных чисел p и q : любая

интервальная раскраска полного двудольного графа Kp,q состоит из интервальных раскрасок его реберно непересекающихся подграфов G1,…,G , каж(o(p,q))2

дый из которых изоморфен графу Ka(p q) a(p q).

ЛИТЕРАТУРА

Harary F. Graph Theory. Addison-Wesley, Reading, MA. 1969.

Давтян Н.Н. О наименьшем и наибольшем возможных числах вершин с интервальным спектром на множестве правильных реберных раскрасок дерева // Мат. воп. киб. и выч. техники. Т. 32. Ер., 2009. СС. 107-111.

Асратян А.С., Камалян Р.Р. Интервальные раскраски ребер мультиграфа // Прикладная математика. Вып. 5. ЕГУ, 1987. СС. 25-34.

Камалян Р.Р. Интервальные раскраски полных двудольных графов и деревьев // Препринт ВЦ АН Арм. ССР и ЕГУ. Ер., 1989. 11 с.

Камалян Р.Р. Интервальные реберные раскраски графов // Дисс. на соиск. уч. степ. канд.ф.-м.н., ИМ СО АН СССР. Новосибирск, 1990.

Камалян Р.Р., Петросян П.А. Единственность интервальной реберной (m + n — 1) раскраски полного двудольного графа Kmn // Proceedings of the CSIT Conference. Yerevan, 2003. РР. 114-117.

ON A STRUCTURE OF INTERVAL COLORINGS OF COMPLETE

BIPARTITE GRAPHS

R.R. Kamalian

It’s proved that if m = Xn, X e N, then an arbitrary interval coloring of the complete bipartite graph Kmn consists of interval colorings of it’s subgraphs

Gj,…, GX, where for t = 1,…, X GT is isomorphic to Kn n, and for arbitrary i, j,

1 < i < j < X, Gi and Gj have no common edge

lpm br^rn.um^ ^rutfbb№ OTauw3£U3Fu ■Ubr^№U-Ubrc ^uft№5HUtt№ uuwb £mdMumU

U^mgntg^mfc t, np tpt m = Xn , X e N , mqm Km n ip^4 qpm$^ ^mJmjm^mU tf^m^mjpmj^U Utp^nttf pmq^mgmfc t Kn n -^U ^qntfnp^ G1,…, GX ^nqtpn^ jhmm^nq tUpmqpm^Utp^ tf^m^mjpmj^U Utp^nL^Utp^g:

УДК 519.17

Материал взят из журнала Вестник выпуск Физико-математические и естественные науки