On the Equality of Domination Number and 2-Domination Number
Küçük Resim Yok
Tarih
2022
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Sciendo
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
The 2-domination number gamma(2)(G) of a graph G is the minimum cardinality of a set D subset of V (G) for which every vertex outside D is adjacent to at least two vertices in D. Clearly, gamma(2)(G) cannot be smaller than the domination number gamma(G). We consider a large class of graphs and characterize those members which satisfy gamma(2) = gamma. For the general case, we prove that it is NP-hard to decide whether gamma(2) = gamma holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.
Açıklama
Anahtar Kelimeler
domination number, 2-domination number, hereditary property, computational complexity, K-Domination, Annihilation Number, Transversal Numbers, Graphs, Bounds
Kaynak
Discussiones Mathematicae Graph Theory
WoS Q Değeri
Q3
Scopus Q Değeri
Q3