Transversal domination in double graphs
[Трансверсальное доминирование в двойных графах]
S. R. Nayakaa,
Puttaswamya,
K. N. Prakashab a P.E.S. College of Engineering, Mandya, Karnataka 571401, India
b Vidyavardhaka College of Engineering, P.B. No.206, Gokulam III Stage, Mysuru 570002, Karnataka, India
Аннотация:
Пусть
$G$ — произвольный граф. Подмножество
$S$ множества всех вершин
$G$ называется доминирующим множеством, если каждая вершина, не входящая в
$S$, примыкает, по меньшей мере, к одной из вершин из
$S$. Доминирующее множество
$S$ называется трансверсальным доминирующим множеством, если
$S$ имеет непустое пересечение с каждым доминирующим множеством минимальной мощности в
$G$. Минимальная мощность трансверсального доминирующего множества называется числом трансверсального доминирования, обозначаемым
$\gamma_{td}(G)$. В данной статье рассматриваются специальные типы графов, называемые двойными графами, получаемыми с помощью операций над графами. Мы изучаем новый параметр доминирования для этих графов. Вычисляется точное значение числа доминирования и числа поперечного доминирования в двойных графах некоторого стандартного класса графов. Кроме того, получены некоторые простые оценки для этих параметров в терминах порядка графа.
Ключевые слова:
поперечное доминирующее множество, число поперечного доминирования, прямое произведение, двойной граф.
УДК:
519.17
MSC: 05C69 Поступила в редакцию: 29.11.2017
Язык публикации: английский
DOI:
10.23671/VNC.2018.4.23388