- •Глава VIII
- •§ 45. Графическая последовательность
- •§ 46. Критерии графичности последовательности
- •§ 47. Реализация графической последовательности с максимальной связностью
- •§ 48. Гамильтонова реализация графической последовательности
- •§ 49. Расщепляемые графы
- •§ 50. Пороговые графы
- •§ 51. Пороговое разложение графа
- •§ 52. Степенное множество графа
§ 52. Степенное множество графа
Степенным множеством графа называется множество степеней его вершин. От степенной последовательности о множество отличается тем, что в нем не учитывается число вершин, имеющих заданную степень, тогда как в степенной последовательности каждое число фигурирует столько раз, степенью скольких вершин оно является.
Степенное множество графаG обозначим через S(G). Так, для графа G, изображенного на рис. 52.1, S(G) = = {1, 2, 3}.
Хотя степенная последовательность графа удовлетворяет определенным условиям, однако степенным множеством графа может быть произвольное множество. Об этом свидетельствует следующая
Теорема 52.1. Любое конечное множество S натуральных чисел является степенным множеством некоторого порогового графа. Минимальный порядок таких графов равен s +1, где s — максимальное число из множества S. Очевидно, что из этой теоремы вытекает
Следствие 52.2. Любое конечное множество целых, неотрицательных чисел является степенным множеством некоторого графа.
Доказательствотеоремы 52.1. Если S(G) = = S, то \G\ ≥ s+ 1, так что нужно только доказать существование подходящего графа G. Утверждение тривиально для одноэлементного множества S, поскольку S(Kn)={n — 1}. Пусть теперь
ипусть, для определенности,п = 2р — четное число. Нужный граф будем искать в виде
где КХ°Н- граф, полученный из графа Н добавлением х доминирующих вершин, а ОУ°Н — граф, полученный из графа Н добавлением у изолированных вершин. Любой граф вида (1) является пороговым. Попытаемся подобрать числа ха и yβ в выражении (1) так, чтобы выполнялось - равенство S(G) = S. Для этого должно быть
Очевидно, что система уравнений (2) относительно неизвестных хi, yj (i =1,p,j =1, р) имеет решение, все координаты которого положительны:
Подставив в выражение (1) числа, определяемые равенствами (3), получим граф G, для которого S(G)=S. Число его вершин равно
Для нечетногоп = 2р + 1 построение аналогично, толь-to вместо формулы (1) используется формула