В теории графов , края изящным график , маркировка представляет собой тип маркировки графа . Это разметка для простых графов, в которых никакие два различных ребра не соединяют одни и те же две различные вершины , никакое ребро не соединяет вершину с самим собой, а граф связан . Маркировка с изящными краями была впервые представлена Шэн-Пинг Ло в его основополагающей статье. [1]
Определение
Для графа G обозначим множество ребер через а вершины на . Пусть д будет кардинальным изи p быть тем из. Как только задана разметка ребер, вершина u графа помечается суммой меток инцидентных ей ребер по модулю p . Или, в символах, индуцированная разметка на вершине u имеет вид
где V ( u ) - метка вершины, а E ( e ) - присвоенное значение ребра, инцидентного u .
Проблема состоит в том, чтобы найти такую разметку для ребер, чтобы все метки от 1 до q использовались один раз, а индуцированные метки на вершинах проходили от 0 до. Другими словами, результирующий набор меток краев должен быть а также для вершин.
Граф G называется грациозным по ребрам, если он допускает разметку с изящными ребрами.
Примеры
Циклы
Рассмотрим цикл с тремя вершинами C 3 . Это просто треугольник. Можно пометить рёбра 1, 2 и 3 и напрямую проверить, что вместе с индуцированной разметкой на вершинах это даёт изящную по рёбру разметку. Подобно дорожкам,граничит с ребрами, когда 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 нечетное, и не грациозно с ребрами, когда оно четно. Это следует из необходимого условия изящности ребер.
Необходимое условие
Ло дал необходимое условие для градации ребер. [1] Это то, что граф с q ребрами и p вершинами является граничным по ребрам, только если
- есть конгруэнтны к по модулю p .
или, в символах,
В литературе это называется состоянием Ло . [3] Это следует из того факта, что сумма меток вершин в два раза больше суммы ребер по модулю p . Это полезно для опровержения грани графа. Например, это можно применить непосредственно к примерам пути и цикла, приведенным выше.
Дальнейшие избранные результаты
- Граф Петерсена не является грациозным по ребрам.
- Звездный граф (центральный узел и м нога длина 1) реберен изящный , когда т является даже и не тогда , когда т является нечетным . [4]
- Граф дружбы граничит с ребром, когда m нечетно, а не когда четно.
- Обычные деревья ,(глубина n с каждым нелистовым узлом, порождающим m новых вершин) граничат с ребром, когда m четно для любого значения n, но не с грациозностью ребер, когда m нечетно. [5]
- Полный граф на п вершинах,, граничит с ребрами, если n не является четным по отдельности ,.
- Лестница графики никогда краев изящные.
Рекомендации
- ^ а б Ло, Шэн-Пин (1985). «О граничных разметках графов». Congressus Numerantium . 50 : 231–241. Zbl 0597.05054 . Неизвестный параметр
|conference=
игнорируется ( справка ) - ^ К. Куан, С. Ли, Дж. Митчем и А. Ван (1988). "О граничных унициклических графах". Congressus Numerantium . 61 : 65–74.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Л. Ли, С. Ли и Дж. Мурти (1988). "О граничных разметках полных графов: решения гипотезы Ло". Congressus Numerantium . 62 : 225–233.
- ^ Д. Смолл (1990). «Обычные (четные) графы-пауки изящны по краям». Congressus Numerantium . 74 : 247–254.
- ^ С. Кабанисс, Р. Лоу, Дж. Митчем (1992). "О граничных регулярных графах и деревьях". Ars Combinatoria . 34 : 129–142.CS1 maint: несколько имен: список авторов ( ссылка )