Geodesic
Making a Dominating Set of a Graph Connected
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 947-962

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

Let G = (V,E) be a graph and S ⊆ V. We say that S is a dominating set of G, if each vertex in V S has a neighbor in S. Moreover, we say that S is a connected (respectively, 2-edge connected or 2-connected) dominating set of G if G[S] is connected (respectively, 2-edge connected or 2-connected). The domination (respectively, connected domination, or 2-edge connected domination, or 2-connected domination) number of G is the cardinality of a minimum dominating (respectively, connected dominating, or 2-edge connected dominating, or 2-connected dominating) set of G, and is denoted γ (G) (respectively γ_1 (G), or γ_2^′ (G), or γ_2 (G)). A well-known result of Duchet and Meyniel states that γ_1 (G) ≤ 3 γ (G) − 2 for any connected graph G. We show that if γ (G) ≥ 2, then γ_2^′ (G) ≥ 5 γ (G) − 4 when G is a 2-edge connected graph and γ_2 (G) ≤ 11 γ (G) − 13 when G is a 2-connected triangle-free graph.
Keywords: independent set, dominating set, connected dominating set 
@article{DMGT_2018_38_4_a5,
     author = {Li, Hengzhe and Wu, Baoyindureng and Yang, Weihua},
     title = {Making a {Dominating} {Set} of a {Graph} {Connected}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {947--962},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a5/}
}
TY  - JOUR
AU  - Li, Hengzhe
AU  - Wu, Baoyindureng
AU  - Yang, Weihua
TI  - Making a Dominating Set of a Graph Connected
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 947
EP  - 962
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a5/
LA  - en
ID  - DMGT_2018_38_4_a5
ER  - 
%0 Journal Article
%A Li, Hengzhe
%A Wu, Baoyindureng
%A Yang, Weihua
%T Making a Dominating Set of a Graph Connected
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 947-962
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a5/
%G en
%F DMGT_2018_38_4_a5
Li, Hengzhe; Wu, Baoyindureng; Yang, Weihua. Making a Dominating Set of a Graph Connected. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 947-962. http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a5/