Interested Article - Грациозная разметка

Грациозная разметка. Вершинная разметка показана чёрным цветом, рёберная — красным

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

Автором термина «грациозная разметка» является Соломон Голомб ; ( англ. ) был первым, кто выделил этот класс разметок и ввёл его под названием $\beta$ -разметки в статье 1967 года про разметки графов. .

Одной из главных недоказанных гипотез в теории графов является гипотеза грациозности деревьев ( англ. Graceful Tree Conjecture ), также известная как гипотеза Рингеля — Коцига по именам сформулировавших её Герхарда Рингеля и ( англ. ), которая утверждает, что все деревья грациозны. По состоянию на 2017 год гипотеза всё ещё не доказана, но из-за простоты формулировки привлекла широкое внимание (вследствие чего появилось много неправильных доказательств), Коциг в своё время даже охарактеризовал массовые попытки доказать её как «заболевание» .

Основные результаты

В оригинальной статье Роса доказал, что эйлеров граф с числом рёбер m ≡ 1 (mod 4) или m ≡ 2 (mod 4) не может быть грациозным. , в ней же показано, что цикл C _n грациозен тогда и только тогда, когда n ≡ 0 (mod 4) или n ≡ 3 (mod 4).

Грациозны все пути , гусеницы , все с совершенным паросочетанием , все колёса , , , , все прямоугольные решётки , а также все n -мерные гиперкубы . Все простые графы с 4 и менее вершинами грациозны, единственными неграциозными простыми графами на пяти вершинах являются 5- цикл ( пятиугольник ), полный граф K ₅ и бабочка .

Грациозны все деревья с числом вершин не более чем 27; этот результат был получен Альдредом и ( англ. ) в 1998 году с помощью компьютерной программы ; совершенствование их подхода (с применением другого вычислительного метода) позволило показать в 2010 году, что все деревья до 35 вершин включительно грациозны — это результат проекта распределённых вычислений Graceful Tree Verification Project под руководством Вэньцзе Фана .

Примечания

Virginia Vassilevska, «Coding and Graceful Labeling of trees.» SURF 2001. от 25 сентября 2006 на Wayback Machine
↑ Rosa, A. Theory of Graphs (Internat. Sympos., Rome, 1966) (неопр.) . — New York: Gordon and Breach, 1967. — С. 349—355 .
Huang, C.; Kotzig, A.; Rosa, A. Further results on tree labellings (неопр.) // Utilitas Mathematica. — 1982. — Т. 21 . — С. 31—48 .
Morgan, David. (неопр.) // Bulletin of the Institute of Combinatorics and its Applications. — 2008. — Т. 53 . — С. 82—85 .
↑ Gallian, Joseph A. (англ.) // (англ.) ( : journal. — 1998; 18-е издание в 2015. — Vol. 5 . — P. Dynamic Survey 6 (electronic), в 1-м издании 43 стр., в 18-м — 389 стр . 15 декабря 2018 года.
Kotzig, Anton. Decompositions of complete graphs into isomorphic cubes (англ.) // Journal of Combinatorial Theory. Series B : journal. — 1981. — Vol. 31 , no. 3 . — P. 292—296 . — doi : .
Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
Aldred, R. E. L.; McKay, Brendan D. Graceful and harmonious labellings of trees (неопр.) // Bulletin of the Institute of Combinatorics and its Applications. — 1998. — Т. 23 . — С. 69—72 .
Fang, Wenjie. (англ.) : journal. — 2010. — arXiv : . 15 августа 2016 года. См. также

Литература

K. Eshghi , Sharif University of Technology, 2002.
U. N. Deshmukh and Vasanti N. Bhat-Nayak, New families of graceful banana trees — Proceedings Mathematical Sciences, 1996 — Springer
M. Haviar, M. Ivaska, Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015.
Ping Zhang, A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, 2016 — Springer