On the equality of domination number and 2-domination number
Makaleler > Tam Makale · 2022
Yazarlar: Gülnaz BORUZANLI EKİNCİ, Csilla Bujtas
Discussiones Mathematicae Graph Theory, SCI Expanded İndekslerine Giren Dergi, Uluslararası, Wos, 2022, cilt 44, ss 383-383
DOI: 10.7151/dmgt.2452
Özet
The 2-domination number γ 2 (G) of a graph G is the minimum cardinality of a set D ⊆ V (G) for which every vertex outside D is adjacent to at least two vertices in D. Clearly, γ 2 (G) cannot be smaller than the domination number γ(G).We consider a large class of graphs and characterize those members which satisfy γ 2 = γ.For the general case, we prove that it is NP-hard to decide whether γ 2 = γ holds.We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.