Граціозна розмітка[1] в теорії графів — така вершинна розмітка графу з ребрами деякою підмножиною цілих чисел між 0 і включно, що різні вершини позначено різними числами, і така, що, якщо кожне ребро позначити абсолютною різницею міток вершин, які воно з'єднує, то всі отримані різниці будуть різними[2]. Граф, який допускає граціозну розмітку, називають граціозним графом.
Автором терміна «граціозна розмітка» є Соломон Ґоломб; Александер Роса був першим, хто виділив цей клас розміток і ввів його під назвою -розмітка в статті 1967 року про розмітки графів.[3].
Однією з головних недоведених гіпотез у теорії графів є гіпотеза граціозності дерев (англ.Graceful Tree Conjecture), також відома як гіпотеза Рінгеля — Коціга за іменами її авторів Герхарда Рінґеля[ru] і Антона Коціга[en], яка стверджує, що всі дерева граціозні. Станом на 2017 гіпотезу все ще не доведено, але простота формулювання привернула широку увагу математиків-аматорів (внаслідок чого з'явилося багато неправильних доведень), Коціг свого часу навіть охарактеризував масові спроби довести її як «хворобу»[4].
Основні результати
В оригінальній статті Роса довів, що ейлерів граф з числом ребер m ≡ 1 (mod 4) або m ≡ 2 (mod 4) не може бути граціозним.[3] У ній же показано, що цикл Cn граціозний тоді і тільки тоді, коли n ≡ 0 (mod 4) або n ≡ 3 (mod 4).
Граціозні всі дерева з числом вершин не більше ніж 27; цей результат отримали 1988 року за допомогою комп'ютерної програми Альдред і Маккей[en][6][8]; удосконалення їхнього підходу (із застосуванням іншого обчислювального методу) дозволило показати 2010 року, що граціозними є всі дерева до 35 вершин включно — це результат проєкту розподілених обчислень Graceful Tree Verification Project під керівництвом Веньцзе Фана[9].
↑Aldred, R. E. L.; McKay, Brendan D. Graceful and harmonious labellings of trees // Bulletin of the Institute of Combinatorics and its Applications. — 1998. — Т. 23 (1 June). — С. 69—72.
