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

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

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

Главной гипотезой в теории графов является гипотеза изящного дерева или Гипотеза Рингеля – Котцига, названная в честь Герхарда Рингеля и Антона Коцига, которая предполагает, что все деревья изящны. Это все еще открытая гипотеза, хотя родственная, но немного более слабая гипотеза, известная как гипотеза Рингеля, была доказана в 2020 году. Гипотеза Рингеля – Котцига также известна как «гипотеза изящной разметки». Коциг однажды назвал попытку доказать гипотезу «болезнью».

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

Другая гипотеза в теории графов - это Гипотеза Розы, названная в честь Александра Розы, которая гласит, что все треугольные кактусы изящны или почти - изящный.

• 1 Избранные результаты
• 2 См. также
• 3 Внешние ссылки
• 4 Ссылки
• 5 Дополнительная литература

• В своей оригинальной статье Роза доказал что граф Эйлера с числом ребер m ≡ 1 (mod 4) или m ≡ 2 (mod 4) не может быть изящным.
• Также в своей оригинальной статье Роза доказал, что цикл C n является изящным тогда и только тогда, когда n ≡ 0 (mod 4) или n ≡ 3 (mod 4).
• Все графы путей и гусеница графы изящны.
• Все графы лобстеров с точным соответствием изящны.
• Все деревья с не более чем 27 вершинами изящны ; этот результат был показан Олдредом и Маккеем в 1998 году с использованием компьютерной программы. Это было распространено на деревья с не более чем 29 вершинами в диссертации Майкла Хортона с отличием. Еще одно расширение этого результата до деревьев с 35 вершинами было заявлено в 2010 году проектом Graceful Tree Verification Project, проектом распределенных вычислений, возглавляемым Вэньцзе Фаном.
• Все колесные графы, веб-графики, графы руля, графы передач и прямоугольные сетки изящны.
• Все n-мерные гиперкубы изящны.
• Все простые графы с четырьмя или менее вершинами изящны. Единственные не изящные простые графы с пятью вершинами - это 5- цикл (пятиугольник ); полный граф K 5 ; и граф-бабочка.

• Edge-изящная разметка
• Список гипотез

• Видео Numberphile о изящной гипотезе о дереве

1. ^Вирджиния Василевска, «Кодирование и изящная маркировка деревьев». SURF 2001. PostScript
2. ^ Роза, А. (1967), «О некоторых оценках вершин графа», Теория графов (Internat. Sympos., Рим, 1966), Нью-Йорк: Гордон и Брич, pp. 349–355, MR 0223271.
3. ^Монтгомери, Ричард; Покровский, Алексей; Судаков, Бенни (2020). «Доказательство гипотезы Рингеля». arXiv : 2001.02665 [math.CO ].
4. ^Huang, C.; Коциг А. ; Роза, А. (1982), «Дальнейшие результаты по разметке деревьев», Utilitas Mathematica, 21 : 31–48, MR 0668845.
5. ^Хартнетт, Кевин. «Радужное доказательство показывает, что у графиков есть однородные части». Журнал Quanta. Проверено 29 февраля 2020 г.
6. ^Huang, C.; Коциг А. ; Роза, А. (1982), «Дальнейшие результаты по разметке деревьев», Utilitas Mathematica, 21 : 31–48, MR 0668845.
7. ^Роза, А. (1988), «Циклический тройной цикл Штейнера. Системы и маркировка треугольных кактусов », Scientia, 1 : 87–95.
8. ^Морган, Дэвид (2008),« Все омары с идеальным соответствием изящны », Бюллетень Института комбинаторики и его приложений, 53 : 82–85, hdl : 10402 / era.26923.
9. ^ Галлиан, Джозеф А. (1998), «Динамический обзор маркировки графов ", Электронный журнал комбинаторики, 5 : Dynamic Survey 6, 43 стр. (389 стр. в 18 изд.) (электронный), MR 1668059.
10. ^Олдред, REL; Маккей, Брендан Д. (1998), «Изящные и гармоничные обозначения деревьев», Бюллетень Института комбинаторики и его приложений, 23 : 69–72, MR 1621760.
11. ^(2003), Graceful Trees: Statistics and Algorithms.
12. ^Fang, Wenjie (2010), A Computational Approach to the Graceful Tree Conjecture, arXiv : 1003.3045, Bibcode : 2010arXiv1003.3045F. См. Также Проект Graceful Tree Verification Project
13. ^Коциг, Антон (1981), «Разложение полных графов на изоморфные кубы», Журнал комбинаторной теории, серия B, 31 (3) : 292–296, doi : 10.1016 / 0095-8956 (81) 90031-9, MR 0638285.
14. ^Вайсштейн, Эрик У. «Изящный график». MathWorld.

• (К. Эшги) Введение в Graceful Graphs, Технологический университет Шарифа, 2002 г.
• (ООН Дешмук и Васанти Н. Бхат- Nayak), Новые семейства изящных банановых деревьев - Proceedings Mathematical Sciences, 1996 - Springer
• (M. Haviar, M. Ivaska), Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015.
• (Пин Чжан ), Калейдоскопический взгляд на раскраски графиков, SpringerBriefs in Mathematics, 2016 - Спрингер