Дискретная математика / Текст лекций по курсу ДМ

Характеризация реберных графов

Граф Gназываетсяреберным графом, если он изоморфен реберному графуL(H) некоторого графа Н. Например,K4 - х есть реберный граф

Покажем, что звезда К_1,3не является реберным графом. Предположим, чтоK_1,3=L(H). Тогда графHимеет 4 ребра, поскольку вK_1,3четыре вершины, и, кроме того, графHдолжен быть связным. Все связные графы с четырьмя ребрами приведены на рис. Так какL(С4)=С4 иL(K_1,3+x)=K₄- х, тоHможет быть только одним из трех деревьев. Но реберными графами этих деревьев являются соответственно простая цепь Р4, граф К₃* К₂и граф К₄. Таким образом К_1,3не есть реберный граф. В дальнейшем мы увидим, что граф К_1,3играет важную роль при установлении основных свойств реберных графов. Первый результат о реберных графах — утверждение (2) приведенной ниже теоремы -полученный Крауцем, довольно близок к самому определению реберного графа. Существенный сдвиг в изучении свойств реберных графов был сделан ван Роои и Вилфом, которым удалось получить (утверждение (3)) структурный критерий того, что данный граф является реберным. Наконец, Байнеке [4] и Робертсон (не опубликовано) нашли все подграфы, которые не могут встречаться в реберных графах. Напомним, что порожденным подграфом называется подграф, максимальный на данном множестве вершин. Треугольник Т графаGназываетсянечетным, если вGимеется вершина, смежная с нечетным числом вершин в Т, ичетнымв противном случае.

Теорема.Следующие утверждения эквивалентны:

(1) G - реберный граф;

(2) ребра графа G можно разбить на полные подграфы таким образом, чтобы ни одна из вершин не принадлежала более чем двум подграфам;

(3) граф G не содержит звезду K1,s в качестве порожденного подграфа, и если два нечетных треугольника имеют общее ребро, то подграф, порожденный их вершинами, есть K4;

(4) ни один из девяти графов, приведенных на рисунке, не является порожденным подграфом графа G.

Доказательство. (1) влечет (2). ПустьG- реберный граф некоторого графаH. Не теряя общности, предположим, что вHнет изолированных вершин. Тогда ребра звезды каждой вершины графа Н порождают полный подграф графаG, и любое ребро графаGпринадлежит только одному такому подграфу. Поскольку каждое ребро графа Н принадлежит звездам ровно двух вершин графа Н, то ни одна из вершин графаGне содержится более чем в двух таких подграфах.

(2) влечет (1). Пусть дано разбиение множества всех ребер графа Gна полные подграфыS1,S2, • • •,Sn, удовлетворяющее утверждению (2). Покажем, как построить граф Н, для которого реберным графом будет графG. Вершины графа Н соответствуют объединению множестваSвсех подграфовS1,S2, ...,Snи множестваUвершин графаG, причем каждую вершину изUмы относим только к одному из подмножествSi. Таким образом, объединениеSUявляется множеством вершин графа Н и две вершины смежны тогда и только тогда, когда соответствующие им множества имеют непустое пересечение, т. е. Н — граф пересеченийQ(SU).

(2) влечет (4). Легко проверить, что ни один из девяти графов, приведенных на рисунке , не допускает разбиение множества ребер на полные подграфы, удовлетворяющее указанному выше условию. Окончательный результат вытекает из того, что каждый порожденный подграф реберного графа сам должен быть реберным графом.

(4) влечет (3). Покажем, что если граф Gне удовлетворяет утверждению (3), то вGнайдется порожденный подграф, изоморфный одному из девяти запрещенных графов. Предположим, чтоGсодержит нечетные треугольникиabcиabd, причем с и а не смежны.

В зависимости от того, существует или нет в графе Gвершинаv, смежная с нечетным числом вершин обоих треугольников, возможны два случая.

Случай 1. Пусть вершина vсмежна с нечетным числом вершин треугольниковabcиabd. Тогда имеются две возможности: илиvсмежна точно с одной вершиной в каждом треугольнике, илиv

смежна с более чем одной вершиной в каждом треугольнике. Если выполняется последнее, то вершина vдолжна быть смежной со всеми четырьмя вершинами двух треугольников, и, следовательно, графGсодержитG3 (см. рис.) как порожденный подграф. При осуществлении первой возможности либо вершинаvсмежна только с одной из вершин а илиb- и тогда получается графG1, либоvсмежна и с вершиной с, и с вершинойd— и тогда получается

граф G2.

Случай 2. Нет вершины, смежной с нечетным числом вершин каждого из этих двух треугольников. Пусть в этом случае вершины uиvсмежны с нечетным числом вершин треугольниковabcиabdсоответственно. Здесь могут быть три подслучая:

Случай 2.1. Каждая вершина uиvсмежна точно с одной вершиной

соответствующего треугольника.

Случай 2.2. Одна из вершин uиvсмежна со всеми тремя вершинами «своего» треугольника, а другая только с одной.

Случай 2.3. Каждая вершина uиvсмежна со всеми тремя вершинами соответствующего треугольника.

Прежде чем рассматривать эти подслучаи, отметим два факта. Если вершина uилиvсмежна с вершиной а илиb, то она смежна также с вершиной с илиd, так

как иначе в графе Gбыл бы порожденный подграфG1. Далее, ниu, ниvне могут быть смежны одновременно с с иd, так как иначе в графеGбыл бы порожденный подграфG2 илиG3.

Случай 2.1. Пусть uс,vdG. В зависимости от того, принадлежит или нет реброuvграфуG, получаемG4 илиG5, в качестве порожденного подграфа. Еслиub,vdG, то из предыдущих замечаний следует, чтоudG,vc!G; еслиuv!G, то вершины {a,d, и,v} порождаютG1, если жеuvG, то вершины {а,b, с,d, и,v} порождаютG8. Пустьub,uaG; тогда обязательноud,vcG. Поэтому, еслиuv!G, то порождается графG8, а еслиwuG, то графG2. Наконец, если .ub,vbG, то опятьud,vcG, откуда следует, что в зависимости от того,

принадлежит или нет ребро uvграфуG, порожденным подграфом графаGбудетG9 илиG1.

Случай 2.2. Пусть uа,ub,uсG. Ясно, что еслиudG, тоG3— порожденный подграф графаG; таким образом,ud!G. Далее, вершинаvможет быть смежной или сd, или сb. ЕслиvdG, то в зависимости от того, принадлежит или нет реброuvграфуG, порожденным подграфом графаGбудетG2 илиG5. ЕслиvbG,то порожденным подграфом графаGбудетG3 илиG1 в зависимости от того, смежна или нет вершинаvс обеими вершинами с иu.

Случай 2.3. Если ud,vcилиuvпринадлежитG, тоG3—порожденный подграф. Оставшаяся единственная возможность приводит к порожденному подграфуG6.

(3) влечет (1). Пусть для графа Gсправедливо утверждение (3). Можно считать графGсвязным. Далее, должно выполняться точно одно из следующих двух условий:

1. Граф Gсодержит два четных треугольника, имеющих общее

ребро,

2. Если два треугольника графа Gимеют общее ребро, то один

из них нечетный.

Можно показать, что если граф Gудовлетворяет первому условию, то он совпадает с одним из графовH1=L(K1,3+x), Н2=L(H1) илиH3=L(K4), изображенных на рисунке. Поэтому предположим, чтоGудовлетворяет второму условию. Приведем метод построения такого графа Н, чтоG=L(H).

Пусть F1— семейство всех клик графаG, не являющихся четными треугольниками, причем каждая такая клика рассматривается как множество вершин, иF3— семейство вершин графаG(которые берутся как отдельные элементы), принадлежащих некоторой клике

К семейства F1 и не смежных ни с одной вершиной графаG- К. Наконец, пустьF3— семейство ребер графаG(каждое ребро взято как множество, состоящее из двух вершин), принадлежащих одному и тому же четному треугольнику. Не трудно проверить, что графGизоморфен реберному графу графа пересечений Н=Q(F1UF2UF3). Теорема доказана.

Последнее построение иллюстрируется на рисунке, где семействами данного графа G, определяющими граф пересечений Н, являются

F1 = {{1, 2, 3, 4}, {4, 5, 6}},F2 = {{1}, {2}, {3}} иF3, = {{5,7}, {6,7}}; таким образом,G=L(H).

Содержание