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

В теории графов дисциплине , математической , частотное разбиение графа ( простой граф ) — это разбиение его вершин, сгруппированных по их степени. Например, последовательность степеней левого графа ниже равна (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. Последовательность степеней правого графа равна 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_f2, (д ₃ ) ^{f ₃}, ..., (д _к ) ^{ж _к}) где степени d _i различны и f _i ≥ f _j для i < j .Бхат-Наяк и др. (1979) показали, что разбиение p на k частей, k ≤ целая часть $(p-1)/2$ это частотный раздел ^[2] эйлерова графа и обратно.

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

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

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

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

Ссылки

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

Внешний раздел

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

[1] Чинн, П.З. (1971), Частотное разбиение графа. Последние тенденции в теории графов , Конспект лекций по математике, вып. 186, Берлин: Springer-Verlag, стр. 69–70.

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

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

[4] * Бхат-Наяк, Васанти Н .; Наик, Ранджан Н. и Рао, С.Б. (1977), «Частотные разбиения: принудительно панциклические и принудительно негамильтоновы последовательности степеней», Discrete Mathematics , 20 : 93–102, doi : 10.1016/0012-365x(77)90049-8

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

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

[7] С.Б. Рао , Обзор теории потенциально p-графических и принудительно p-графических последовательностей, в: под редакцией С.Б. Рао, Конспекты лекций по комбинаторике и теории графов по математике, Vol. 885 (Шпрингер, Берлин, 1981), 417–440.

[1]

[2]

[3]

[4]

[5]

[6]

[7]