Расщепляемые графы

Некоторые свойства графов полностью определяются стененными последовательностями, т. е. либо присущи всем реализациям степенной последовательности, либо и одной из них. Одно из таких свойств — расщепляемость.

Граф G называется расщепляемым, если существует разбиение множества его вершин на клику и независимое множество, т. е. такое разбиение

AUB = VG, (1)

что порожденный подграф G(A) является полным, G(B) —пустым. Это разбиение называется полярным. Множество А называется верхней долей графа G, а В — нижней; одна из этих долей может быть пустой.

Как подтверждает простая проверка, все графы порядка п ≥ 3 расщепляемы, но уже среди четырехвершинных графов есть и расщепляемые и не расщепляемые.

Для правильной графической последовательности d преведем параметр m(d), положив

т(d) = max {i: di ≥ i—l}.

Например, m(d)=3 для d = (4², 2², I²).

Теорема 49.1 (П. Хаммер, Б. Симеоне, 1981 г.). Пустъ d — правильная графическая п-последовательностъ, G — ее произвольная реализация. Граф G расщепляем тогда и только тогда, когда верно равенство

где m = m(d).

Пусть G — расщепляемый граф. Среди всех полярных разбиений множества VG выберем разбиение (1) с максимальным числом вершин в верхней доле. Очевидно, что если а € А, b € В и I А I = k, то deg а ≥ k — 1, deg b < k. Следовательно, m = к. Поскольку G (А) = К_т, G(В) = О_п-m, то верно равенство (2).

Обратно, пусть для некоторого графа G VG = {1, 2,....., п }, deg i = di. Положим A = {1, 2,..., т }, В = { m + l,..., п) и сумму степеней вершин из А разобьем на две части:

где С — вклад, вносимый в эту сумму ребрами вида а₁а₂ , а_i € А, а D — тот вклад, который вносят ребра вида ab, а € А, b € В. Очевидно, что верны неравенства

Равенство (2) верно только тогда, когда оба неравенства (3) являются равенствами. Но это и означает, что G(A) = К_т , G(B) = Оп-т.

Очевидно

Следствие 49.2. Если одна из реализаций графиче­ской последовательности расщепляема, то и все ее реали­зации расщепляемы.

Графическая последовательность называется расщеп­ляемой, если она имеет расщепляемую реализацию.

При доказательстве достаточности выполнения усло­вия (2) для расщепляемости графической последователь­ности d не были использованы ни смысл параметра m(d), ни то, что последовательность d не возрастает. Поэтому верно

Утверждение 49.3. Для расщепляемости графиче­ской п-последователъности d необходимо и достаточно, чтобы для какого-либо m, l≤m≤n, выполнялось ра­венство (2).

Расщепляемые графы составляют важный и содержа­тельный класс графов. В частности, он включает в себя все пороговые графы, рассматриваемые в следующем па­раграфе. Некоторые задачи, сложные в общей ситуации (например, задача построения наибольшего независимого множества), становятся тривиальными в классе расщеп­ляемых графов. Другие задачи для этого класса графов столь же сложны, как и для произвольных графов. Из­вестно, например, что проблема изоморфизма произволь­ных графов просто сводится к аналогичной проблеме для расщепляемых графов (см. [18]).

Характеризация расщепляемых графов в терминах запрещенных порожденных подграфов приведена в § 62.