Набор дружественных индексов

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

Дружественная маркировка $n-$ вершинного неориентированного графа $G = (V, E)$ определяется как присвоение значений 0 и 1 вершинам $G$ со свойством, при котором число вершин, помеченных 0, максимально близко к количество вершин, отмеченных цифрой 1: они должны быть либо равны (для графов с четным числом вершин), либо отличаться на единицу (для графов с нечетным числом вершин).

Учитывая дружественную маркировку вершин графа $G$ , можно также пометить ребра: данное ребро $uv$ помечается цифрой 0, если его конечные точки $u$ и $v$ имеют одинаковые метки, и помечается цифрой 1, если его конечные точки имеют разные метки. разметки Дружественный индекс — это абсолютное значение разницы между количеством ребер, помеченных 0, и количеством ребер, помеченных 1.

Дружественный набор индексов G $,$ обозначаемый $FI (G)$ , представляет собой набор чисел, которые могут возникнуть как дружественные индексы дружественных $G.$ разметок ^[1]

Динамический обзор маркировки графов содержит список статей, в которых исследуются дружественные индексы различных графов. ^[2]

Ссылки

^ Квонг, Харрис; Ли, Син-Мин; Нг, Хо (2008). «О дружественных индексных множествах 2-регулярных графов» . Дискретная математика . 308 (23): 5522–5532. дои : 10.1016/j.disc.2007.10.018 . МР 2459372 .
^ Галлиан, Джозеф А. (2009). «Динамический обзор разметки графов» (PDF) . Эл. Ж. Комбинат . 16 (#DS6).

Эта теории графов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[1] Квонг, Харрис; Ли, Син-Мин; Нг, Хо (2008). «О дружественных индексных множествах 2-регулярных графов» . Дискретная математика . 308 (23): 5522–5532. дои : 10.1016/j.disc.2007.10.018 . МР 2459372 .

[2] Галлиан, Джозеф А. (2009). «Динамический обзор разметки графов» (PDF) . Эл. Ж. Комбинат . 16 (#DS6).

[1]

[2]