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

Edge-graceful labeling

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

Определение

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

{ Displaystyle V (u) = Sigma E (e) mod | V (G) |}

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

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

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

Примеры

Циклы

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

{ displaystyle C_ {5}}

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

Пути

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

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

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

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

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

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

{ Displaystyle ; д (д + 1)}

является конгруэнтный к

{ displaystyle { frac {p (p-1)} {2}}}

по модулю п.

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

{ Displaystyle д (д + 1) экв { гидроразрыва {р (р-1)} {2}} mod р.}

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

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

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

Navigation