Geodesic
On the equality of domination number and 2-domination number
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 383-406

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: domination number, $2$-domination number, hereditary property, computational complexity 
@article{DMGT_2024_44_1_a19,
     author = {Boruzanl{\i} Ekinci, G\"ulnaz and Bujt\'as, Csilla},
     title = {On the equality of domination number and 2-domination number},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {383--406},
     publisher = {mathdoc},
     volume = {44},
     number = {1},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a19/}
}
TY  - JOUR
AU  - Boruzanlı Ekinci, Gülnaz
AU  - Bujtás, Csilla
TI  - On the equality of domination number and 2-domination number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 383
EP  - 406
VL  - 44
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a19/
LA  - en
ID  - DMGT_2024_44_1_a19
ER  - 
%0 Journal Article
%A Boruzanlı Ekinci, Gülnaz
%A Bujtás, Csilla
%T On the equality of domination number and 2-domination number
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 383-406
%V 44
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a19/
%G en
%F DMGT_2024_44_1_a19
Boruzanlı Ekinci, Gülnaz; Bujtás, Csilla. On the equality of domination number and 2-domination number. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 383-406. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a19/