Розмітка графа

Граціозна розмітка. Мітки вершин показано чорними цифрами, мітки ребер — червоними.

Граф називають граціозним, якщо його вершини розмічено числами від 0 до |E|, розміру графу, і ця розмітка породжує реберну розмітку від 1 до |E|. Для будь-якого ребра e мітка ребра дорівнює додатній різниці між мітками вершин цього ребра. Іншими словами, якщо ребро e інцидентне двом вершинам з мітками i і j, то ребро e отримує мітку |i − j|. Таким чином, граф G = (V, E) є граціозним тоді і тільки тоді, коли існує вкладення, яке породжує бієкцію з E в додатні цілі числа аж до |E|.

У своїй роботі Роза довів, що всі ейлерові цикли розміру, порівнянного з 1 або 2 (за модулем 4), граціозними не є. Які сімейства графів є граціозними, нині інтенсивно досліджується. Можливо, найвизначнішою недоведеною гіпотезою в галузі розмітки графів є гіпотеза Рінгеля — Коціга, яка стверджує, що всі дерева граціозні. Це доведено для всіх шляхів, гусениць і багатьох інших нескінченних сімейств дерев. Сам Коціг назвав спробу довести гіпотезу «порочною»[6].

Реберна граціозна розмітка простих графів (графів без петель і кратних ребер) з p вершинами і q ребрами — це розмітка ребер різними цілими числами з набору {1, …, q}, така, що розмітка вершин сумами міток суміжних ребер за модулем p включає всі значення від 0 до p − 1. Кажуть, що граф G реберно граціозний, якщо дозволяє реберну граціозну розмітку.

Реберну граціозну розмітку першим увів 1985 року С. Ло[7].

Необхідною умовою існування для графу реберної розмітки є умова Ло:

${\displaystyle q(q+1)=p/(p-1)2\mod p.}$

Гармонійна розмітка графу G — це вкладення множини вершин графу G в групу цілих чисел за модулем k, де k — число ребер графу G, яке породжує бієкцію між ребрами графу G і числами за модулем k вибором як мітки ребра (x, y) суми міток двох вершин x, y (mod k). Гармонійний граф — це граф, що має гармонійну розмітку. Непарні цикли є гармонійними графами, як і граф Петерсена. Є гіпотеза, що всі дерева є гармонійними графами, якщо дозволити одну вершину використовувати повторно[8]. Книга з сімома сторінками K_1,7 × K₂ є прикладом негармонійного графу[9].

Коректне розфарбування вершин графу найменшим набором кольорів — трьома.

Розфарбування графу є підкласом розмітки графу. Вершинне розфарбування призначає різні мітки суміжним вершинам, реберне розфарбування призначає різні мітки суміжним ребрам.

Щаслива розмітка графу G — це призначення додатних цілих чисел вершинам графу G так, що, якщо S(v) означає суму міток сусідніх вершин вершини v, то S є розфарбуванням вершин графу G. Щасливе число графу G — це таке найменше k, що граф G має щасливу розмітку цілими числами {1, …, k}[10].