CN-реберное доминирование в графах

Алварди А. , Сонер Н.
Владикавказский математический журнал. 2013. Том 15. Выпуск 2.С.12-18.

Аннотация:
Пусть \(G=(V,E)\) - граф. Подмножество \(D\) множества \(V\) называется реберно доминирующим множеством с общей окрестностью (CN-реберно доминирующим множеством), если для любой вершины \(v\in V-D\) существует вершина \(u\in D\) такая, что \(uv\in E(G)\) и \(|\Gamma(u,v)|\geq 1\), где \(|\Gamma(u,v)|\)- множество общих соседей вершин \(u\) и \(v\). Наименьшая мощность такого CN-реберно доминирующего множества обозначается \(\gamma_{cn}(G)\) и называется реберно доминирующим числом с общей окрестностью (CN-реберно доминирующим числом) графа \(G\). В данной статье вводятся понятия реберно доминирующего числа с общей окрестностью и реберно доматического числа с общей окрестностью (CN-реберно доматического числа) в графе, найдены их точные значения в некоторых стандартных графах, установлены границы и некоторые интересные результаты.

Ключевые слова: реберно доминирующее множество с общей окрестностью, реберно доматическое число с общей окрестностью, реберно доминирующее число с общей окрестностью

Язык статьи: Английский Загрузить полный текст