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/

[1] L. Arseneau, A. Finbow, B. Hartnell, A. Hynick, D. MacLean and L. O’Sullivan, On minimal connected dominating sets, J. Combin. Math. Combin. Comput. 24 (1997) 185–191.

[2] C. Bo and B. Liu, Some inequalities about the connected domination number, Discrete Math. 159 (1996) 241–245. doi:10.1016/0012-365X(95)00088-E

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, London, 2008).

[4] M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, k-domination and k-independence in graphs: A survey, Graphs Combin. 28 (2012) 1–55. doi:10.1007/s00373-011-1040-3

[5] C.J. Colbourn and L.K. Stewart, Permutaion graphs: Connected domination and Steiner trees, Discrete Math. 86 (1990) 179–189. doi:10.1016/0012-365X(90)90359-P

[6] D.-Z. Du and P.-J. Wan, Connected Dominating Set: Theory and Applications (Springer, New York, 2013). doi:10.1007/978-1-4614-5242-3

[7] Y.L. Du and H.W. Du, A new bound on maximum independent set and minimum connected dominating set in unit disk graphs, J. Comb. Optim. 30 (2015) 1173–1179. doi:10.1007/s10878-013-9690-0

[8] P. Duchet and H. Meyniel, On Hadwiger’s number and the stability number, North-Holland Math. Studies 62 (1982) 71–73. doi:10.1016/S0304-0208(08)73549-7

[9] S. Guha and S. Khuller, Approximation algorithms for connected dominating sets, Algorithmica 20 (1998) 374–387. doi:10.1007/PL00009201

[10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: The Theory (Marcel Dekker, New York, 1997).

[11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Selected Topics (Marcel Dekker, New York, 1997).

[12] M. Li, P.-J. Wan and F. Yao, Tighter approximation bounds for minimum CDS in unit disk graphs, Algorithmica 61 (2011) 1000–1021. doi:10.1007/s00453-011-9512-7

[13] X. Li and Z. Zhang, Two algorithms for minimum 2- connected r-hop dominating set, Inform. Process. Lett. 110 (2010) 986–991. doi:10.1016/j.ipl.2010.08.008

[14] M. Moscarini, Doubly chordal graphs, Steiner trees, and connected domination, Networks 23 (1993) 59–69. doi:10.1002/net.3230230108

[15] E. Sampathkumar and H.B. Walikar, The connected domination number of a graphs, J. Math. Phys. Sci. 13 (1979) 607–613.

[16] E. Vigoda, Lecture Notes on a Parallel Algorithm for Generating a Maximal Independent Set, Georgia Institute of Technology, last updated for 7530 – Randomized Algorithms, Spring 2010.

[17] P.-J.Wan, L.Wang and F. Yao, Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks, in: IEEE ICDCS (2008) 337–344. doi:10.1109/ICDCS.2008.15

[18] K. White, M. Farber and W.R. Pulleyblank, Steiner trees, connected domination and strongly chordal graphs, Networks 15 (1985) 109–124. doi:10.1002/net.3230150109

[19] W. Wu, H. Du, X. Jia, Y. Li and S. Huang, Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theoret. Comput. Sci. 352 (2006) 1–7. doi:10.1016/j.tcs.2005.08.037

[20] W. Wu, X. Gao, P.M. Pardalos and D.-Z. Du, Wireless networking, dominating and packing, Optim. Lett. 4 (2010) 347–358. doi:10.1007/s11590-009-0151-8