Реберный граф

Пусть S — непустое множество, a F = { S₁, S₂,......, S_n }— его покрытие непустыми несовпадающими подмножествами. Определим граф W(F) следующими условиями: V W(F) = F, вершины S_i и S_j смежны, если i ¹ j и S _iÇ S_j ¹ Æ. Произвольный граф G называется графом пересечений, если и только если существуют такое множество S и такое покрытие этого множества F, что G W(F).

Утверждение 10.1. Любой граф является графом пересечений.

> Пусть G — граф, VG = (1, 2,..., n), S — множество элементов графа G. Для i = обозначим через S_i множество, составленное из вершины i и всех инцидентных ей ребер. Положив F = { S₁, S₂,..., S_n }, получим G W(F). <

Важный класс графов пересечений составляют реберные графы. Для произвольного графа G реберный граф L (G)определяется следующими двумя условиями:

1) VG (G) =EG,

2) вершины e ₁ и e ₂смежны в L (G)тогда и только тогда, когда ребра e₁ и e₂ смежны в G.

Если для некоторого графа H существует такой граф G, что H L (G), то H также называется реберным графом.

На рис. 10.1 совмещены два графа — G и L (G). Вершины графа G — темные кружочки, вершины графа L (G)— светлые кружки. Ребра графа G — тонкие линии, ребра графа L (G) — жирные линии.

Утверждение 10.2. Если d₁, d₂,..., d_n — степенная последовательность (n, m) -графа G, то L (G) является (m, l) -графом, где

> Очевидно, что i -я вершина графа G порождает

ребер графа L (G), поэтому

Очевидно, что если графы G и H изоморфны, то L (G)и L (H)также изоморфны. В то же время справедливы соотношения L (K ₃) L (K _1,3) = K ₃. X. Уитни доказал, что K ₃и K _1,3— единственная пара несовпадающих связных графов, имеющих один и тот же реберный граф. Если порядок хотя бы одного из рассматриваемых графов меньше пяти, то это проверяется непосредственно, а для графов больших порядков вытекает из следующей теоремы.

Теорема 10.3 (X. Уитни, 1932 г.). Пусть G и H — связные графы, | G |>4, | H |>4 и L (G) L (H). Тогда G H и, более того, для всякого изоморфизма j: L (G) ->L (H) существует единственный изоморфизм y: G ->H, индуцирующий j, т. е. такой, что j(e) = y(u) y (v) для любого ребра e = uv графа G.

> Изоморфизм j реберных графов L (G)и L (H) будем рассматривать как биекцию EG->EH между множествами ребер графов G и H, при которой смежным ребрам соответствуют смежные, а несмежным — несмежные.

Лемма 10.4. Если ребра e_i (i = ) составляют звезду K _{1, r} в графе G, то их образы j(e_i) составляют такую же звезду K _{1, r} в графе H.

> Доказательство леммы. При r =2 утверждение леммы верно по определению изоморфизма графов. Пусть r= 3и ребра e ₁, e ₂, e ₃составляют в графе G звезду K _1,3. Поскольку граф G связен и порядок его более четырех, то в нем есть четвертое ребро e, смежное с каждым из ребер e _iили точно с одним из них. Таким же свойством обладает j(e) по отношению к j(e_i). Ребра j(e_i) составляют в графе H либо звезду K _1,3, либо треугольник. Но ребро, смежное с каким-либо ребром треугольника, смежно ровно с двумя из ребер. Тем самым доказано, что ребра j(e_i) составляют звезду в графе H. Нужное утверждение доказано для r = 3. Очевидно, что для r >3 оно просто получается по индукции. <

Поскольку отображение j^-1: L (H)-> L (G)также является изоморфизмом реберных графов, то из предыдущей леммы вытекает следующее утверждение: ребра e_i (i = ) составляют максимальную (относительно включения) звезду K_1,r в графе G тогда и только тогда, когда их образы j(e_i) составляют максимальную звезду K _1,rв графе H.

Итак, изоморфизм j определяет биекцию между множествами максимальных звезд графов G и H. Очевидно, что в каждой из этих звезд более одного ребра, и потому в ней есть лишь одна центральная вершина. Максимальную звезду графа G с центром x обозначим через S_G (x). Очевидно, что если j(S_G (x)) = S_H (x'), то соответствие y: x -> x' является инъекцией множества всех вершин графа G, не являющихся концевыми, в аналогичное подмножество вершин графа H. Из соображений симметрии следует, что y— биекция.

Теперь распространим действие отображения y на концевые вершины графа G. Пусть v — одна из таких вершин. В графе G есть смежная с ней вершина x степени большей, чем 1. Положим xv = e и выберем в звезде S_H (x')такое ребро e' = x'v', что j(e) = e'. Покажем, что

Пусть это не так. Тогда в звезде S_H (v')есть ребро e ₁' = e'. Следовательно, в звезде j^-1(S_H (v')) есть ребро e₁ = j^-1(e ₁'), смежное с ребром e, но не входящее в S_G (x). Но тогда вершина v — конец этого ребра и deg v ¹1. Равенство (1) доказано.

Положив y(v) = v', получим инъекцию множества концевых вершин графа G в множество концевых вершин графа H. Из соображений симметрии теперь следует, что y — биекция.

Итак, построена биекция y: VG -> VH. Докажем, что эта биекция является графовым изоморфизмом. Сохраним обозначение S_G (x)и в том случае, когда deg x = 1. В этой ситуации S_G (x)содержит одно ребро, инцидентное вершине x, и не является максимальной звездой. Смежность вершин x и y в графе G означает, что звезды S_G (x)и S_G (y)имеют общее ребро. Поэтому

Доказано, что y: G -> H — изоморфизм графов. Из определения отображения y видно, что оно индуцирует j, т. е. j(e) = x'y'= y(x) y(y)для любого ребра e = xy Î EG. Существование нужного изоморфизма y доказано.

Остается доказать единственность. Пусть, напротив, есть два изоморфизма y₁¹ y ₂, удовлетворяющих условию теоремы. Тогда y₁(a) ¹ jy(a) для некоторой вершины a Î VG. Рассмотрим
произвольное ребро e = ax в графе G. Тогда

и, следовательно, y₂(x) = y₁(a). Если deg a > 1 и ay — другое ребро G, то аналогично получаем y₂(y) = y₁(a)=y₂(x), что противоречит инъективности y₂. Если же deg a =1, то из y₂(x) = y₁(a) получаем deg x = 1, что противоречит связности G. <

Известно, что не всякий граф является реберным, например, звезда K _1,3не есть реберный граф. (Характеризация реберных графов имеется в книге [7].) Однако класс реберных графов достаточно содержателен. Об этом свидетельствует, в частности, тот факт, что гипотеза реберной реконструируемости произвольных графов эквивалентна гипотезе вершинной реконструируемости реберных графов. Приведем без доказательства следующую теорему.

Теорема 10.5 (Р. Хемминджер, 1969 г.). Связный граф G с более чем тремя ребрами реберно реконструируем тогда и только тогда, когда реберный граф L (G) вершинно реконструируем.

Отметим еще любопытную связь, существующую между матрицей инцидентности графа G и матрицей смежности реберного графа L (G).

Утверждение 10.6. Если I = I (G) — матрица инцидентности графа G и A = A (L (G)) — матрица смежности графа L (G), записанная при той же, что и I, нумерации ребер, то

где E — единичная матрица порядка |EG|.

> Рассмотрим элемент произведения I ^T I, занимающий позицию (k, l):

Последняя сумма равна числу вершин графа G, инцидентных обоим ребрам с номерами k и l. При k = l это число равно 2. Если k ¹ l, то это число по определению есть элемент Au матрицы A. Равенство (2) доказано. <

Следствие 10.7. Любой корень характеристического полинома всякого реберного графа не меньше, чем –2.

> Пусть G — реберный граф. Тогда для него верно равенство (2). С другой стороны, пусть Ax = l x для ненулевого вектора x. Тогда I^TIx= (l + 2) x (в силу равенства (2)). Теперь рассмотрим квадрат длины вектора lx:

Следовательно,