Граціозна розмітка

Граціозна розмітка. Вершинну розмітку показано чорним кольором, реберну — червоним

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

Автором терміна «граціозна розмітка» є Соломон Ґоломб; Александер Роса був першим, хто виділив цей клас розміток і ввів його під назвою $\beta$-розмітка в статті 1967 року про розмітки графів..

Однією з головних недоведених гіпотез у теорії графів є гіпотеза граціозності дерев (Шаблон:Lang-en), також відома як гіпотеза Рінгеля — Коціга за іменами її авторів Шаблон:Нп і Шаблон:Iw, яка стверджує, що всі дерева граціозні. Шаблон:Станом на гіпотезу все ще не доведено, але простота формулювання привернула широку увагу математиків-аматорів (внаслідок чого з'явилося багато неправильних доведень), Коціг свого часу навіть охарактеризував масові спроби довести її як «хворобу».

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

В оригінальній статті Роса довів, що ейлерів граф з числом ребер m ≡ 1 (mod 4) або m ≡ 2 (mod 4) не може бути граціозним. У ній же показано, що цикл C_n граціозний тоді і тільки тоді, коли n ≡ 0 (mod 4) або n ≡ 3 (mod 4).

Граціозні всі шляхи, гусениці, всі Шаблон:Не перекладено з досконалим паруванням, всі колеса, Шаблон:Не перекладено, Шаблон:Не перекладено, всі прямокутні решітки, а також всі n-вимірні гіперкуби. Всі прості графи з 4 і менше вершинами граціозні, неграціозними простими графами на п'яти вершинах є тільки 5-цикл (п'ятикутник), повний граф K₅ і метелик.

Граціозні всі дерева з числом вершин не більше ніж 27; цей результат отримали 1988 року за допомогою комп'ютерної програми Альдред і Шаблон:Iw; удосконалення їхнього підходу (із застосуванням іншого обчислювального методу) дозволило показати 2010 року, що граціозними є всі дерева до 35 вершин включно — це результат проєкту розподілених обчислень Graceful Tree Verification Project під керівництвом Веньцзе Фана.

Література

• K. Eshghi Introduction to Graceful Graphs Шаблон:Webarchive, 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