Изящная маркировка

В теории графов изящная маркировка графа разностью с $m$ ребрами — это маркировка его вершин некоторым подмножеством целых чисел от 0 до $m$ включительно, такая, что никакие две вершины не имеют общей метки, а каждое ребро однозначно идентифицируется абсолютной . между его конечными точками, так что эта величина лежит между 1 и $m$ включительно. ^[1] Граф, допускающий изящную разметку, называется изящным графом .

Название «изящная маркировка» принадлежит Соломону В. Голомбу ; Этот тип разметки первоначально был назван β-мечением Александром Розой в статье 1967 года о разметке графов. ^[2]

Основной открытой проблемой в теории графов является гипотеза изящного дерева или гипотеза Рингеля-Коцига , названная в честь Герхарда Рингеля и Антона Коцига , а иногда и сокращенно GTC (не путать с гипотезой Коцига о графах с регулярной связностью). ^[3] Предполагается, что все деревья изящны. Это все еще открытая гипотеза, хотя родственная, но более слабая гипотеза, известная как «гипотеза Рингеля», была частично доказана в 2020 году. ^[4]^[5]^[6] Коциг однажды назвал попытку доказать эту гипотезу «болезнью». ^[7]

Другая более слабая версия изящной маркировки — это почти изящная маркировка , в которой вершины могут быть помечены с использованием некоторого подмножества целых чисел на $[0, m + 1]$ так, что никакие две вершины не имеют общей метки, и каждое ребро однозначно идентифицируется абсолютная разница между его концами (эта величина лежит на $[1, m + 1]$ ).

Другая гипотеза в теории графов — гипотеза Розы , названная в честь Александра Розы, которая гласит, что все треугольные кактусы изящны или почти изящны. ^[8]

изящный граф с ребрами от 0 до $m имеет не менее$ Предполагается, что $\left\lceil {\sqrt {3m+{\tfrac {9}{4}}}}\right\rfloor$ вершин из-за скудных результатов линейки . Эта гипотеза проверена для всех графов с 213 и менее ребрами.

Изящный граф с 27 ребрами и 9 вершинами.

Избранные результаты

В своей оригинальной статье Роза доказал, что эйлеров граф с числом ребер m ≡ 1 (mod 4) или m ≡ 2 (mod 4) не может быть изящным. ^[2]
Также в своей оригинальной статье Роза доказал, что цикл Cn _n изящный тогда и только тогда, когда ≡ 0 (mod 4) или n ≡ 3 (mod 4).
Все графы путей и графы-гусеницы изящны. ^[2]
Все графы-омары с идеальным соответствием изящны. ^[9]
Все деревья, имеющие не более 27 вершин, изящны; этот результат был показан Олдредом и Маккеем в 1998 году с помощью компьютерной программы. ^[10]^[11] В дипломной работе Майкла Хортона с отличием это было распространено на деревья с не более чем 29 вершинами. ^[12] Еще одно распространение этого результата на деревья с 35 вершинами было заявлено в 2010 году проектом Graceful Tree Verification Project, проектом распределенных вычислений, возглавляемым Вэньцзе Фаном. ^[13]
Все графики колес , веб-графики, графики руля , графики передач и прямоугольные сетки изящны. ^[10]
Все n -мерные гиперкубы изящны. ^[14]
Все простые связные графы с четырьмя и менее вершинами являются изящными. Единственные неизящные простые связные графы с пятью вершинами — это 5- цикл ( пентагон ); полный граф К ₅ ; и график-бабочка . ^[15]

См. также

Ссылки

^ Вирджиния Василевска , «Кодирование и изящная маркировка деревьев». СЕРФ 2001. Постскриптум
^ Перейти обратно: ^а ^б ^с Роза, А. (1967), «О некоторых оценках вершин графа», Теория графов (Международный симпозиум, Рим, 1966) , Нью-Йорк: Гордон и Брич, стр. 349–355, MR 0223271 .
^ Ван, Тао-Мин; Ян, Ченг-Чанг; Сюй, Лих-Синг; Ченг, Эдди (2015), «Бесконечное множество эквивалентных версий гипотезы об изящном дереве», Applicable Analysis and Discrete Mathematics , 9 (1): 1–12, doi : 10.2298/AADM141009017W , MR 3362693
^ Монтгомери, Ричард; Покровский, Алексей; Судаков, Бенни (2020). «Доказательство гипотезы Рингеля». arXiv : 2001.02665 [ math.CO ].
^ Хуанг, К.; Коциг, А .; Роза, А. (1982), «Дальнейшие результаты по маркировке деревьев», Utilitas Mathematica , 21 : 31–48, MR 0668845 .
^ Хартнетт, Кевин. «Радужное доказательство показывает, что графики состоят из однородных частей» . Журнал Кванта . Проверено 29 февраля 2020 г.
^ Хуанг, К.; Коциг, А .; Роза, А. (1982), «Дальнейшие результаты по маркировке деревьев», Utilitas Mathematica , 21 : 31–48, MR 0668845 .
^ Роза, А. (1988), «Циклические тройные системы Штейнера и маркировка треугольных кактусов», Scientia , 1 : 87–95 .
^ Морган, Дэвид (2008), «Все лобстеры с идеальным совпадением изящны», Бюллетень Института комбинаторики и ее приложений , 53 : 82–85, hdl : 10402/era.26923 .
^ Перейти обратно: ^а ^б Галлиан, Джозеф А. (1998), «Динамический обзор разметки графов» , Электронный журнал комбинаторики , 5 : Динамический обзор 6, 43 стр. (389 стр. в 18-м изд.) (электронный), MR 1668059 .
^ Олдред, REL; Маккей, Брендан Д. (1998), «Изящные и гармоничные разметки деревьев», Бюллетень Института комбинаторики и ее приложений , 23 : 69–72, MR 1621760 .
^ Хортон, Майкл П. (2003), Изящные деревья: статистика и алгоритмы .
^ Фанг, Вэньцзе (2010), Вычислительный подход к гипотезе изящного дерева , arXiv : 1003.3045 , Bibcode : 2010arXiv1003.3045F . См. также проект Graceful Tree Verification Project.
^ Коциг, Антон (1981), «Разложение полных графов на изоморфные кубы», Журнал комбинаторной теории, серия B , 31 (3): 292–296, doi : 10.1016/0095-8956(81)90031-9 , MR 0638285 .
^ Вайсштейн, Эрик В. «Изящный график» . Математический мир .

Внешние ссылки

Дальнейшее чтение

(К. Эшги) Введение в изящные графы , Технологический университет Шарифа, 2002 г.
(У.Н. Дешмук и Васанти Н. Бхат-Наяк), Новые семейства изящных банановых деревьев – Труды математических наук, 1996 – Springer
(М. Хавиар, М. Иваска), Маркировка вершин простых графов, Исследования и разъяснения по математике, Том 34, 2015.
( Пин Чжан ), Калейдоскопический взгляд на раскраски графов, SpringerBriefs in Mathematics, 2016 – Springer

[Vas2001-1] Вирджиния Василевска , «Кодирование и изящная маркировка деревьев». СЕРФ 2001. Постскриптум

[Ros1967-2] Перейти обратно: ^а ^б ^с Роза, А. (1967), «О некоторых оценках вершин графа», Теория графов (Международный симпозиум, Рим, 1966) , Нью-Йорк: Гордон и Брич, стр. 349–355, MR 0223271 .

[3] Ван, Тао-Мин; Ян, Ченг-Чанг; Сюй, Лих-Синг; Ченг, Эдди (2015), «Бесконечное множество эквивалентных версий гипотезы об изящном дереве», Applicable Analysis and Discrete Mathematics , 9 (1): 1–12, doi : 10.2298/AADM141009017W , MR 3362693

[4] Монтгомери, Ричард; Покровский, Алексей; Судаков, Бенни (2020). «Доказательство гипотезы Рингеля». arXiv : 2001.02665 [ math.CO ].

[5] Хуанг, К.; Коциг, А .; Роза, А. (1982), «Дальнейшие результаты по маркировке деревьев», Utilitas Mathematica , 21 : 31–48, MR 0668845 .

[6] Хартнетт, Кевин. «Радужное доказательство показывает, что графики состоят из однородных частей» . Журнал Кванта . Проверено 29 февраля 2020 г.

[Hua1982-7] Хуанг, К.; Коциг, А .; Роза, А. (1982), «Дальнейшие результаты по маркировке деревьев», Utilitas Mathematica , 21 : 31–48, MR 0668845 .

[Rosa1988-8] Роза, А. (1988), «Циклические тройные системы Штейнера и маркировка треугольных кактусов», Scientia , 1 : 87–95 .

[Morgan-9] Морган, Дэвид (2008), «Все лобстеры с идеальным совпадением изящны», Бюллетень Института комбинаторики и ее приложений , 53 : 82–85, hdl : 10402/era.26923 .

[Gal2015-10] Перейти обратно: ^а ^б Галлиан, Джозеф А. (1998), «Динамический обзор разметки графов» , Электронный журнал комбинаторики , 5 : Динамический обзор 6, 43 стр. (389 стр. в 18-м изд.) (электронный), MR 1668059 .

[11] Олдред, REL; Маккей, Брендан Д. (1998), «Изящные и гармоничные разметки деревьев», Бюллетень Института комбинаторики и ее приложений , 23 : 69–72, MR 1621760 .

[Horton2003-12] Хортон, Майкл П. (2003), Изящные деревья: статистика и алгоритмы .

[13] Фанг, Вэньцзе (2010), Вычислительный подход к гипотезе изящного дерева , arXiv : 1003.3045 , Bibcode : 2010arXiv1003.3045F . См. также проект Graceful Tree Verification Project.

[Kot1981-14] Коциг, Антон (1981), «Разложение полных графов на изоморфные кубы», Журнал комбинаторной теории, серия B , 31 (3): 292–296, doi : 10.1016/0095-8956(81)90031-9 , MR 0638285 .

[Mat2007-15] Вайсштейн, Эрик В. «Изящный график» . Математический мир .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]