Введение

Тип раскраски графа

В теории графов, грациозная раскраска графа — это тип раскраски графа для простых связных графов, в которых любые две различные рёбра не соединяют одни и те же две различные вершины, и ни одно ребро не соединяет вершину саму с собой. Грациозные раскраски графов были впервые введены Шэн Пин Ло в его основополагающей работе.

Определение

Учитывая граф G, мы обозначаем множество его ребер E(G) и множество его вершин V(G). Пусть q – кардинальность E(G), а p – кардинальность V(G). Если задана маркировка ребер, то вершина графа маркируется суммой маркировок ребер, инцидентных ей, по модулю p. Или, в символах, индуцированная маркировка вершины задается следующим образом:

где V(u) – полученное значение для вершины u, а E(e) – значение маркировки ребра e, инцидентного вершине u. Задача состоит в том, чтобы найти маркировку ребер таким образом, чтобы все метки от 1 до q использовались ровно один раз, а индуцированные метки вершин принимали значения от 0 до p – 1. Иными словами, результирующий набор меток для ребер должен быть {1, 2, ..., q}, причем каждое значение используется один раз, а для вершин – {0, 1, ..., p – 1}. Граф G называется допустимым к маркировке, если существует такая маркировка.

Циклы

Рассмотрим цикл с тремя вершинами, это просто треугольник. Можно обозначить рёбра числами 1, 2 и 3 и непосредственно проверить, что вместе с индуцированной маркировкой на вершинах это даёт изящную раскраску рёбер. Подобно путям, граф является изящным по рёбрам, когда m нечётно, и не является таковым, когда m чётно.

Пути

Рассмотрим путь с двумя вершинами. Здесь единственная возможность — пометить единственный ребро графа числом 1. Индуцированные метки на обеих вершинах равны 1. Следовательно, данный граф не является краевым изящным. Добавление ребра и вершины к данному графу дает путь с тремя вершинами. Обозначим вершины как , , и . Пронумеруем два ребра следующим образом: ребро обозначим 1, а ребро — 2. Тогда индуцированные метки на вершинах , , и будут равны 1, 0 и 2 соответственно. Это краевая изящная маркировка, и, следовательно, данный граф является краевым изящным. Аналогично, можно проверить, что не является краевым изящным. В общем случае, является краевым изящным, когда m нечетно, и не является краевым изящным, когда m четно. Это следует из необходимого условия краевой изящности.

Необходимое условие

Ло дал необходимое условие для графа с q ребрами и p вершинами, чтобы быть реберно-грациозным: это следует из того факта, что сумма меток вершин равна удвоенной сумме меток ребер по модулю p. Это полезно для доказательства того, что граф не является реберно-грациозным. Например, это можно непосредственно применить к приведенным выше примерам пути и цикла.

Дополнительные результаты

Граф Петерсена не является грациозным по рёбрам. Звёздный граф (центральный узел и m «ног» длиной 1) является грациозным по рёбрам, когда m чётно, и не является грациозным по рёбрам, когда m нечётно. Граф дружбы является грациозным по рёбрам, когда m нечётно, и не является грациозным по рёбрам, когда m чётно. Регулярные деревья (глубина n, с каждым нелистовым узлом, испускающим m новых вершин) являются грациозными по рёбрам, когда m чётно для любого значения n, но не являются грациозными по рёбрам, когда m нечётно. Полный граф на n вершинах, Kn, является грациозным по рёбрам, если только n не является двойно чётным. Лестничный граф никогда не является грациозным по рёбрам.