Geodesic
Domination Parameters of a Graph and its Complement
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 203-215.

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

A dominating set in a graph G is a set S of vertices such that every vertex in V (G) S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.
Keywords: domination, complement, total domination, connected domination, clique domination, restrained domination 
@article{DMGT_2018_38_1_a16,
     author = {Desormeaux, Wyatt J. and Haynes, Teresa W. and Henning, Michael A.},
     title = {Domination {Parameters} of a {Graph} and its {Complement}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {203--215},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a16/}
}
TY  - JOUR
AU  - Desormeaux, Wyatt J.
AU  - Haynes, Teresa W.
AU  - Henning, Michael A.
TI  - Domination Parameters of a Graph and its Complement
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 203
EP  - 215
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a16/
LA  - en
ID  - DMGT_2018_38_1_a16
ER  - 
%0 Journal Article
%A Desormeaux, Wyatt J.
%A Haynes, Teresa W.
%A Henning, Michael A.
%T Domination Parameters of a Graph and its Complement
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 203-215
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a16/
%G en
%F DMGT_2018_38_1_a16
Desormeaux, Wyatt J.; Haynes, Teresa W.; Henning, Michael A. Domination Parameters of a Graph and its Complement. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 203-215. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a16/

[1] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976) 711–712. doi:10.1090/S0002-9904-1976-14122-5

[2] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194–197. doi:10.1017/S030500410002168X

[3] F. Buckley and M. Lewinter, A Friendly Introduction to Graph Theory (Prentice Hall Inc., New Jersey, 2003).

[4] Y. Caro, D.B. West and R. Yuster, Connected domination and spanning trees with many leaves, SIAM J. Discrete Math. 13 (2000) 202–211. doi:10.1137/S0895480199353780

[5] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, Fifth Edition (Chapman and Hall/CRC, 2010) pp. 598.

[6] B. Das and V. Bhargavan, Routing in ad-hoc networks using minimum connected dominating sets, IEEE International Conference on Communications (ICC 97), June 1997. doi:10.1109/ICC.1997.605303

[7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).

[8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998).

[9] M.A. Henning, Recent results on total domination in graphs: A survey, Discrete Math. 309 (2009) 32–63. doi:10.1016/j.disc.2007.12.044

[10] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013).

[11] F. Jaeger and C. Payan, Relations du type Nordhaus-Gaddum pour le nombre d’absorption d’un graphe simple, C.R. Acad. Sci. Paris 274 (1972) 728–730.

[12] D. Li, H. Du, P.J. Wan, X. Gao, Z. Zhang and W. Wu, Construction of strongly connected dominating sets in asymmetric multi-hop wireless networks, Theoret. Comput. Sci. 410 (2009) 661–669. doi:10.1016/j.tcs.2008.09.058

[13] H. Karami, A. Khodkar, S.M. Sheikholeslami and D.B. West, Connected domination number of a graph and its complement, Graphs Combin. 28 (2012) 189–197. doi:10.1007/s00373-011-1028-z

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

[15] O. Schaudt, On graphs for which the connected domination number is at most the total domination number, Discrete Appl. Math. 160 (2012) 281–284. doi:10.1016/j.dam.2011.12.025

[16] V.G. Vizing, A bound on the external stability number of a graph, Dokl. Akad. Nauk 164 (1965) 729–731.

[17] J. Wu and H. Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, in: Proc. 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications ACM (1999) 7–14. doi:10.1145/313239.313261