Трансверсальное доминирование в двойных графах

Наяка С. Р. , Путтасвами , Пракаша К. Н.
Владикавказский математический журнал. 2018. Том 20. Выпуск 4.С.59-66.

Аннотация:
Пусть \(G\) - произвольный граф. Подмножество \(S\) множества всех вершин \(G\) называется доминирующим множеством, если  каждая вершина, не входящая в \(S\), примыкает, по меньшей мере, к одной из вершин из \(S\).  Доминирующее множество \(S\) называется трансверсальным доминирующим множеством, если \(S\)  имеет непустое пересечение с каждым доминирующим множеством минимальной мощности в \(G\).  Минимальная мощность трансверсального доминирующего множества называется числом  трансверсального доминирования, обозначаемым \(\gamma_{td}(G)\). В данной статье  рассматриваются специальные типы графов, называемые двойными графами, получаемыми с  помощью операций над графами. Мы изучаем новый параметр доминирования для этих графов.  Вычисляется точное значение числа доминирования и числа поперечного доминирования в  двойных графах некоторого стандартного класса графов. Кроме того, получены некоторые  простые оценки для этих параметров в терминах порядка графа.

Ключевые слова: поперечное доминирующее множество, число поперечного доминирования, прямое произведение, двойной граф

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

+ Список литературы