Частотное разбиение графика

В теории графов , дисциплине в математике , частотное разбиение графа ( простого графа ) представляет собой разбиение его вершин, сгруппированных по их степени. Например, последовательность степеней левого графа ниже равна (3, 3, 3, 2, 2, 1), а его частотное разбиение равно 6 = 3 + 2 + 1. Это означает, что у него есть 3 вершины с некоторой степенью, 2 вершины с некоторой другой степенью и 1 вершина с третьей степенью. Последовательность степеней двудольного графа в середине ниже равна (3, 2, 2, 2, 2, 2, 1, 1, 1), а его частотное разбиение равно 9 = 5 + 3 + 1. Последовательность степеней правого графа ниже равна (3, 3, 3, 3, 3, 3, 2), а его частотное разбиение равно 7 = 6 + 1.

График с частотным разбиением 6 = 3 + 2 + 1.
Двудольный граф с частотным разбиением 9 = 5 + 3 + 1.
График с частотным разбиением 7 = 6 + 1.

В общем случае существует много неизоморфных графов с заданным частотным разбиением. Граф и его дополнение имеют одно и то же частотное разбиение. Для любого разбиения p = f ₁ + f ₂ + ... + f _k целого числа p > 1, отличного от p = 1 + 1 + 1 + ... + 1, существует по крайней мере один (связанный) простой граф, имеющий это разбиение в качестве своего частотного разбиения. ^[1]

Частотные разбиения различных семейств графов полностью идентифицированы; частотные разбиения многих семейств графов не идентифицированы.

Частотные разбиения графов Эйлера

Для частотного разбиения p = f ₁ + f ₂ + ... + f _k целого числа p > 1 его графическая последовательность степеней обозначается как ((d ₁ ) ^{f ₁} ,(d ₂ ) ^{f ₂} , (d ₃ ) ^{f ₃} , ..., (d _k ) ^{f _k} ), где степени d _i различны и f _i ≥ f _j для i < j . Бхат-Наяк и др. (1979) показали, что разбиение p с k частями, k ≤ целой части, является частотным разбиением ^[2] эйлерова графа и наоборот. $(p-1)/2$

Частотное разбиение деревьев, гамильтоновы графы, турниры и гиперграфы

Были охарактеризованы частотные разбиения семейств графов , таких как деревья ^{[3] ,} гамильтоновы графы ^[4], ориентированные графы и турниры ^[5] и k-однородные гиперграфы ^[6] .

Нерешенные проблемы в частотных разбиениях

Частотные разбиения следующих семейств графов еще не охарактеризованы:

Ссылки

^ Чинн, П. З. (1971), Частотное разбиение графа. Последние тенденции в теории графов , Lecture Notes in Mathematics, т. 186, Берлин: Springer-Verlag, стр . 69–70
^ Рао, Сиддани Бхаскара; Бхат-Наяк, Васанти Н.; Наик, Ранджан Н. (1979), «Характеристика частотных разбиений эйлеровых графов», Труды симпозиума по теории графов (Индийский статистический институт, Калькутта, 1976) , ISI Lecture Notes, т. 4, Macmillan of India, Нью-Дели, стр. 124–137 , MR 0553937. Также в Lecture Notes in Mathematics, Combinatorics and Graph Theory, Springer-Verlag , New York, Vol. 885 (1980), p. 500.
^ Рао, ТМ (1974), «Частотные последовательности в графах», Журнал комбинаторной теории, Серия B , 17 : 19–21 , doi : 10.1016/0095-8956(74)90042-2
^ * Bhat-Nayak, Vasanti N.; Naik, Ranjan N. & Rao, SB (1977), "Частотные разбиения: принудительно панциклические и принудительно негамильтоновы последовательности степеней", Discrete Mathematics , 20 : 93–102 , doi : 10.1016/0012-365x(77)90049-8
^ Alspach, B. & Reid, KB (1978), «Частоты степеней в орграфах и турнирах», Журнал теории графов , 2 (3): 241– 249, doi :10.1002/jgt.3190020307
^ Бхат-Наяк, В. Н. и Наик, Р. Н. ( 1985 ), «Частотные разбиения k-однородных гиперграфов», Utilitas Math. , 28 : 99–104
^ SB Rao , Обзор теории потенциально p-графических и принудительно p-графических последовательностей, в: SB Rao edit., Combinatorics and Graph Theory Lecture Notes in Math., Vol. 885 (Springer, Berlin, 1981), 417-440

Внешняя часть

Берге, К. (1989), Гиперграфы, комбинаторика конечных множеств , Амстердам: Северная Голландия, ISBN 0-444-87489-5

[1] Чинн, П. З. (1971), Частотное разбиение графа. Последние тенденции в теории графов , Lecture Notes in Mathematics, т. 186, Берлин: Springer-Verlag, стр . 69–70

[2] Рао, Сиддани Бхаскара; Бхат-Наяк, Васанти Н.; Наик, Ранджан Н. (1979), «Характеристика частотных разбиений эйлеровых графов», Труды симпозиума по теории графов (Индийский статистический институт, Калькутта, 1976) , ISI Lecture Notes, т. 4, Macmillan of India, Нью-Дели, стр. 124–137 , MR 0553937. Также в Lecture Notes in Mathematics, Combinatorics and Graph Theory, Springer-Verlag , New York, Vol. 885 (1980), p. 500.

[3] Рао, ТМ (1974), «Частотные последовательности в графах», Журнал комбинаторной теории, Серия B , 17 : 19–21 , doi : 10.1016/0095-8956(74)90042-2

[4] * Bhat-Nayak, Vasanti N.; Naik, Ranjan N. & Rao, SB (1977), "Частотные разбиения: принудительно панциклические и принудительно негамильтоновы последовательности степеней", Discrete Mathematics , 20 : 93–102 , doi : 10.1016/0012-365x(77)90049-8

[5] Alspach, B. & Reid, KB (1978), «Частоты степеней в орграфах и турнирах», Журнал теории графов , 2 (3): 241– 249, doi :10.1002/jgt.3190020307

[6] ^ Бхат-Наяк, В. Н. и Наик, Р. Н. ( 1985 ), «Частотные разбиения k-однородных гиперграфов», Utilitas Math. , 28 : 99–104

[7] SB Rao , Обзор теории потенциально p-графических и принудительно p-графических последовательностей, в: SB Rao edit., Combinatorics and Graph Theory Lecture Notes in Math., Vol. 885 (Springer, Berlin, 1981), 417-440