On the equality of domination number and 2-domination number
Articles > Article · 2022
Authors: Gülnaz BORUZANLI EKİNCİ, Csilla Bujtas
Discussiones Mathematicae Graph Theory, Journal Indexed in SCI Expanded, International, WoS, 2022, vol 44, pp 383-383
DOI: 10.7151/dmgt.2452
Summary
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.