Совершенная разметка рёбер

Совершенная (или грациозная) разметка рёбер графа — это вид разметки графа. Это разметка для простых графов (в простом графе никакие два различных ребра не соединяют те же самые две различные вершины, никакое ребро не соединяет вершину с ней же (нет петель) и граф связен). Совершенные разметки рёбер ввёл в своей статье С. Ло.

Определение

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

$V(u)=\Sigma E(e)\mod |V(G)|$

где V(u) — метка для вершины, а E(e) — назначенное значение метки ребра, инцидентного u.

Задача заключается в нахождении разметки рёбер такой, что в качестве меток используются все числа от 1 до q по одному разу и порождённые метки вершин принимают значения от 0 до p − 1. Другими словами, результирующим множеством меток для рёбер должно быть $\{1,2\dots q\}$ и $\{0,1\dots p-1\}$ для вершин.

Говорят, что граф G рёберно совершенен, если в нём доступна совершенная разметка рёбер.

Примеры

Пути

Представим путь с двумя вершинами, P₂. Единственной возможной разметкой будет 1 в качестве метки ребра. Инцидентные метки двух вершин будут иметь значение 1. Таким образом P₂ не рёберно совершенен.

Добавление ребра и вершины к P₂ даёт P₃, путь с тремя вершинами. Обозначим вершины через v₁, v₂ и v₃. Разметим рёбра следующим образом: ребро (v₁, v₂) пометим 1, а ребро (v₂, v₃) пометим 2. Порождённой разметкой вершин v₁, v₂ и v₃ будет тогда 1, 0 и 2 соответственно. Это совершенная разметка рёбер, а следовательно P₃ является рёберно совершенным.

Аналогично можно проверить, что P₄ не является рёберно совершенным.

В общем случае P_m рёберно совершенен, когда m нечётно, и не рёберно совершенен, когда m нечётно. Это следует из необходимого условия рёберного совершенства (см. ниже).

Циклы

Представим цикл с тремя вершинами, C₃. Это просто треугольник. Можно пронумеровать рёбра числами 1, 2 и 3 и проверить, что порождённая разметка вершин даёт рёберно совершенную разметку.

Подобно путям, $C_{m}$ рёберно совершенен когда m нечётно и несовершенен, когда m чётно.

Рёберно совершенная разметка $C_{5}$ показана на рисунке:

Условие необходимости

С. Ло дал необходимое условие, чтобы граф был рёберно совершенным — граф с q рёбрами и p вершинами является рёберно совершенным только если

$\;q(q+1)$ сравнимо с ${\frac {p(p-1)}{2}}$ по модулю p,

или

$q(q+1)\equiv {\frac {p(p-1)}{2}}\mod p.$

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

Некоторые другие графы

• Граф Петерсена не является рёберно совершенным.
• Граф-звезда $S_{m}$ (центральная вершина и m лучей длины 1) является рёберно совершенным, когда m чётно и несовершенным, когда m нечётно.
• Граф дружеских отношений $F_{m}$ является рёберно совершенным, когда m нечётно и несовершенным, когда m чётно.
• Регулярные деревья, $T_{m,n}$ (глубиной n, к каждой нелистовой вершине прикрепляется m новых вершин) является рёберно совершенным, когда m чётно для любого значения n, но несовершенным, когда m нечётно.
• Полный граф с n вершинами, $K_{n}$, является рёберно совершенным, если $n\neq 2\mod 4$.
• Никакая лестница не является рёберно совершенным графом.