On the Equality of Domination Number and 2-Domination Number

Küçük Resim Yok

Tarih

2022

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

Cilt

Sayı

Künye