В теории графов изящная маркировка графа с m ребрами — это маркировка его вершин некоторым подмножеством целых чисел от 0 до m включительно, при этом никакие две вершины не имеют общей метки, а каждое ребро однозначно идентифицируется абсолютной разницей между его конечными точками, так что эта величина лежит в диапазоне от 1 до m включительно. [1] Граф, допускающий изящную маркировку, называется изящным графом .
Название «изящная маркировка» принадлежит Соломону В. Голомбу ; первоначально этому типу маркировки было дано название β-маркировка Александром Розой в статье 1967 года о маркировке графов. [2]
Крупной открытой проблемой в теории графов является гипотеза об изящном дереве или гипотеза Рингеля–Коцига , названная в честь Герхарда Рингеля и Антона Коцига , а иногда сокращенно GTC (не путать с гипотезой Коцига о регулярно путе-связных графах). [3]
Она предполагает, что все деревья изящны. Это все еще открытая гипотеза, хотя связанная, но более слабая гипотеза, известная как «гипотеза Рингеля», была частично доказана в 2020 году. [4] [5] [6]
Коциг однажды назвал усилия по доказательству этой гипотезы «болезнью». [7]
Другой более слабой версией изящной маркировки является почти изящная маркировка , в которой вершины могут быть помечены с использованием некоторого подмножества целых чисел на [0, m + 1] таким образом, что никакие две вершины не имеют общей метки, а каждое ребро однозначно идентифицируется абсолютной разницей между его конечными точками (эта величина лежит на [1, m + 1] ).
Другая гипотеза в теории графов — гипотеза Розы , названная в честь Александра Розы, которая гласит, что все треугольные кактусы изящны или почти изящны. [8]
Изящный граф с ребрами от 0 до m , как предполагается, имеет не менее вершин, из-за разреженных результатов линейки . Эта гипотеза была проверена для всех графов с 213 или менее ребрами.
Изящный граф с 27 ребрами и 9 вершинами
Избранные результаты
В своей оригинальной статье Роза доказал, что эйлеров граф с числом ребер m ≡ 1 (mod 4) или m ≡ 2 (mod 4) не может быть изящным. [2]
Также в своей оригинальной статье Роза доказал, что цикл C n является изящным тогда и только тогда, когда n ≡ 0 (mod 4) или n ≡ 3 (mod 4).
Все деревья с максимум 27 вершинами являются изящными; этот результат был показан Олдредом и Маккеем в 1998 году с помощью компьютерной программы. [10] [11] Это было распространено на деревья с максимум 29 вершинами в почетной диссертации Майкла Хортона. [12] Другое распространение этого результата до деревьев с 35 вершинами было заявлено в 2010 году проектом Graceful Tree Verification Project, проектом распределенных вычислений под руководством Вэньцзе Фана. [13]
^ abc Rosa, A. (1967), «О некоторых оценках вершин графа», Теория графов (Международные симпозиумы, Рим, 1966) , Нью-Йорк: Gordon and Breach, стр. 349–355, MR 0223271.
^ Ван, Тао-Мин; Ян, Ченг-Чан; Сюй, Ли-Син; Ченг, Эдди (2015), «Бесконечно много эквивалентных версий гипотезы об изящном дереве», Прикладной анализ и дискретная математика , 9 (1): 1–12, doi : 10.2298/AADM141009017W , MR 3362693
^ Хуан, К.; Коциг, А .; Роза, А. (1982), «Дальнейшие результаты по маркировке деревьев», Utilitas Mathematica , 21 : 31–48, MR 0668845.
^ Хартнетт, Кевин. «Rainbow Proof показывает, что графики имеют однородные части». Журнал Quanta . Получено 29.02.2020 .
^ Хуан, К.; Коциг, А .; Роза, А. (1982), «Дальнейшие результаты по маркировке деревьев», Utilitas Mathematica , 21 : 31–48, MR 0668845.
^ Роза, А. (1988), «Циклические тройные системы Штейнера и маркировка треугольных кактусов», Scientia , 1 : 87–95.
^ Морган, Дэвид (2008), «Все омары с идеальными соответствиями грациозны», Бюллетень Института комбинаторики и ее приложений , 53 : 82–85, hdl :10402/era.26923.
^ ab Gallian, Joseph A. (1998), "Динамический обзор маркировки графов", Electronic Journal of Combinatorics , 5 : Dynamic Survey 6, 43 стр. (389 стр. в 18-м изд.) (электронный), MR 1668059.
^ Олдред, Р.Э.Л.; Маккей, Брендан Д. (1998), «Изящная и гармоничная маркировка деревьев», Бюллетень Института комбинаторики и ее приложений , 23 : 69–72, MR 1621760.
^ Хортон, Майкл П. (2003), Изящные деревья: статистика и алгоритмы.
^ Фан, Вэньцзе (2010), Вычислительный подход к гипотезе об изящном дереве , arXiv : 1003.3045 , Bibcode : 2010arXiv1003.3045F. См. также проект Graceful Tree Verification.
^ Коциг, Антон (1981), «Разложение полных графов на изоморфные кубы», Журнал комбинаторной теории, Серия B , 31 (3): 292–296, doi : 10.1016/0095-8956(81)90031-9 , MR 0638285.
