Изящная маркировка
В теории графов изящная маркировка графа с 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 или менее ребрами.
