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

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

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

Определение

Для данного графа $G$ мы обозначаем множество его ребер как $E (G)$ , а множество его вершин как $V (G)$ . Пусть $q$ будет мощностью E $($ $G$ $)$ , а $p$ будет мощностью $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, \dots, q}$ , каждое значение используется один раз, а для вершин он должен быть ${0, 1, \dots, p - 1}$ .

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

Примеры

Циклы

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

Пути

Рассмотрим путь с двумя вершинами, $P 2.$ Здесь единственная возможность — пометить единственное ребро в графе как 1. Индуцированная маркировка на двух вершинах — обе 1. Поэтому $P 2$ не является рёберно-грациозным.

Добавление ребра и вершины к $P 2$ дает $P 3$ , путь с тремя вершинами. Обозначим вершины через $v 1$ , $v 2$ и $v 3$ . Пометим два ребра следующим образом: ребро $(v 1, v 2)$ помечено как 1, а $(v 2, v 3)$ помечено как 2. Тогда индуцированные маркировки на $v 1$ , $v 2$ и $v 3$ равны 1, 0 и 2 соответственно. Это грациозная маркировка, и поэтому $P 3$ является грациозной.

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

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

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

$Ло дал необходимое условие для того ,$ чтобы граф с $q$ ребрами и $p$ вершинами был грациозным по ребрам: ^[1] $q (q + 1)$ должно быть конгруэнтно ⁠ $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}п ( п – 1)/2⁠ mod p$ . В символах:

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

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

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

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

Ссылки

^ ab Lo, Sheng-Ping (1985). «О грациозной маркировке графов». Congressus Numerantium . Конференция Сандэнса, Юта. Т. 50. С. 231–241. Zbl 0597.05054.
^ Q. Kuan, S. Lee, J. Mitchem и A. Wang (1988). «О рёберно-грациозных унициклических графах». Congressus Numerantium . 61 : 65–74.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Л. Ли, С. Ли и Г. Мурти (1988). «О грациозных маркировках полных графов: решения гипотезы Ло». Congressus Numerantium . 62 : 225–233.
^ Д. Смолл (1990). «Обычные (четные) паучьие графы имеют изящные ребра». Congressus Numerantium . 74 : 247–254.
^ S. Cabaniss, R. Low, J. Mitchem (1992). «О регулярных графах и деревьях с изящными рёбрами». Ars Combinatoria . 34 : 129–142.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )