Разметка графа

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

Граф называется грациозным, если его вершины размечены числами от 0 до |E|, размера графа, и эта разметка порождает рёберную разметку от 1 до |E|. Для любого ребра e метка ребра 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].