Изящная маркировка

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

Изящные по краям маркировки были впервые представлены Шэн-Пин Ло в его основополагающей статье.

Определение

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

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

где V ( u ) — результирующее значение для вершины u , а E ( e ) — существующее значение ребра e, инцидентного u .

Задача состоит в том, чтобы найти такую ​​маркировку ребер, чтобы все метки от 1 до q использовались один раз, а индуцированные метки на вершинах проходили от 0 до p – 1 . Другими словами, результирующий набор меток для ребер должен быть {1, 2, …, q } , каждое значение используется один раз, а для вершин должно быть {0, 1, …, p – 1} .

Граф G называется изящным по ребрам, если он допускает изящную по ребрам разметку.

Примеры

Циклы

Изящная маркировка C ₅

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

Пути

Рассмотрим путь с двумя вершинами P ₂ . Здесь единственная возможность — пометить единственное ребро в графе 1. Индуцированные метки на обеих вершинах равны 1. Таким образом, P ₂ не является изящным по ребрам.

ребра и вершины к P2 _— дает P3 _{Добавление} путь с тремя вершинами. Обозначим вершины через v ₁ , v ₂ и v ₃ . Пометьте два ребра следующим образом: ребро ( v ₁ , v ₂ ) помечено 1, а ( v ₂ , v ₃ ) помечено 2. Индуцированные метки на v ₁ , v ₂ и v ₃ тогда равны 1, 0. и 2 соответственно. Это маркировка с изящными краями, поэтому P ₃ является изящным с краями.

Аналогично можно проверить, что P ₄ не является изящным по краям.

В общем, P _m является изящным по краям, когда m нечетное, и не изящным, когда оно четное. Это следует из необходимого условия изящности ребер.

Обязательное условие

Ло дал необходимое условие для того, чтобы граф с q ребрами и p вершин был изящным по ребрам: q ( ​​q + 1) должно конгруэнтно быть ⁠ п ( п – 1) / 2 ⁠ мод п . В символах:

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

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

Дальнейшие избранные результаты

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