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

Edge-graceful labeling

В теория графов, грациозный разметка графиков - это разновидность маркировка графиков. Это маркировка для простые графики в котором нет двух разных края соединить те же два разных вершины, никакое ребро не соединяет вершину с самим собой, и граф связаны. Маркировка с изящными краями была впервые представлена ​​Шэн-Пинг Ло в его основополагающей статье.[1]

Определение

Учитывая график грамм, обозначим множество ребер через а вершины на . Позволять q быть мощность из и п быть тем из . Как только обозначение ребер задано, вершина ты графа помечается суммой меток инцидентных ему ребер по модулю п. Или, в символах, индуцированная разметка на вершине ты дан кем-то

куда V(ты) - метка вершины, а E(е) - присвоенное значение ребра, инцидентного ты.

Проблема состоит в том, чтобы найти такие метки для краев, чтобы все метки от 1 до q используются один раз, а индуцированные метки на вершинах идут от 0 до . Другими словами, результирующий набор меток краев должен быть и для вершин.

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

Примеры

Циклы

Этикетка с изящными краями C5
Изящная маркировка

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

Пути

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

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

Аналогичным образом можно проверить, что п4 не грациозно.

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

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

Ло дал необходимое условие для градации ребер графа.[1] Это то, что граф с q края и п вершины граничат с ребром, только если

является конгруэнтный к по модулю п.

или, в символах,

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

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

Рекомендации

  1. ^ а б Ло, Шэн-Пин (1985). "О граничных разметках графов". Congressus Numerantium. 50: 231–241. Zbl 0597.05054.
  2. ^ К. Куан, С. Ли, Дж. Митчем и А. Ван (1988). "О граничных унициклических графах". Congressus Numerantium. 61: 65–74.CS1 maint: несколько имен: список авторов (связь)
  3. ^ Л. Ли, С. Ли и Дж. Мурти (1988). "О граничных разметках полных графов: решения гипотезы Ло". Congressus Numerantium. 62: 225–233.
  4. ^ Д. Смолл (1990). «Регулярные (четные) графы-пауки граничат с границами». Congressus Numerantium. 74: 247–254.
  5. ^ С. Кабанисс, Р. Лоу, Дж. Митчем (1992). "О граничных регулярных графах и деревьях". Ars Combinatoria. 34: 129–142.CS1 maint: несколько имен: список авторов (связь)