Geodesic
Restrained Domination in Self-Complementary Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 633-645.

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

A self-complementary graph is a graph isomorphic to its complement. A set S of vertices in a graph G is a restrained dominating set if every vertex in V(G) S is adjacent to a vertex in S and to a vertex in V(G) S. The restrained domination number of a graph G is the minimum cardinality of a restrained dominating set of G. In this paper, we study restrained domination in self-complementary graphs. In particular, we characterize the self-complementary graphs having equal domination and restrained domination numbers.
Keywords: domination, complement, restrained domination, self-complementary graph 
@article{DMGT_2021_41_2_a17,
     author = {Desormeaux, Wyatt J. and Haynes, Teresa W. and Henning, Michael A.},
     title = {Restrained {Domination} in {Self-Complementary} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {633--645},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a17/}
}
TY  - JOUR
AU  - Desormeaux, Wyatt J.
AU  - Haynes, Teresa W.
AU  - Henning, Michael A.
TI  - Restrained Domination in Self-Complementary Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 633
EP  - 645
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a17/
LA  - en
ID  - DMGT_2021_41_2_a17
ER  - 
%0 Journal Article
%A Desormeaux, Wyatt J.
%A Haynes, Teresa W.
%A Henning, Michael A.
%T Restrained Domination in Self-Complementary Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 633-645
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a17/
%G en
%F DMGT_2021_41_2_a17
Desormeaux, Wyatt J.; Haynes, Teresa W.; Henning, Michael A. Restrained Domination in Self-Complementary Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 633-645. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a17/

[1] J. Akiyama and F. Harary, A graph and its complement with specified properties. IV. Counting self-complementary blocks, J. Graph Theory 5 (1981) 103–107. doi:10.1002/jgt.3190050108

[2] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241–249. doi:10.1002/jgt.3190030306

[3] E.J. Cockayne, O. Favaron, C.M. Mynhardt and J. Puech, A characterization of (γ, i)-trees, J. Graph Theory 34 (2000) 277–292.

[4] W.J. Desormeaux, T.W. Haynes and M.A. Henning, Domination parameters of a graph and its complement, Discuss. Math. Graph Theory 38 (2018) 203–215. doi:10.7151/dmgt.2002

[5] G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R. Laskar and L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61–69. doi:10.1016/S0012-365X(99)00016-3

[6] G.S. Domke, J.H. Hattingh, M.A. Henning and L.R. Markus, Restrained domination in trees, Discrete Math. 211 (2000) 1–9. doi:10.1016/S0012-365X(99)00036-9

[7] M. Dorfling, W. Goddard, M.A. Henning and C.M. Mynhardt, Construction of trees and graphs with equal domination parameters, Discrete Math. 306 (2006) 2647–2654. doi:10.1016/j.disc.2006.04.031

[8] P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963) 295–315. doi:10.1007/BF01895716

[9] R.A. Gibbs, Self-complementary graphs, J. Combin. Theory Ser. B 16 (1974) 106–123. doi:10.1016/0095-8956(74)90053-7

[10] A. Hansberg, B. Randerath and L. Volkmann, Claw-free graphs with equal 2-domination and domination numbers, Filomat 30 (2016) 2795–2801. doi:10.2298/FIL1610795H

[11] J.H. Hattingh and M.A. Henning, Characterizations of trees with equal domination parameters, J. Graph Theory 34 (2000) 142–153. doi:10.1002/1097-0118(200006)34:2h142::AID-JGT3i3.0.CO;2-V

[12] J.H. Hattingh and E.J. Joubert, Equality in a bound that relates the size and the restrained domination number of a graph, J. Comb. Optim. 31 (2016) 1586–1608. doi:10.1007/s10878-015-9843-4

[13] J.H. Hattingh and E.J. Joubert, The product of the total restrained domination numbers of a graph and its complement, Australas. J. Combin. 70 (2018) 297–308.

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

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

[16] M.A. Henning, Graphs with large restrained domination number, Discrete Math. 197/198 (1999) 415–429. doi:10.1016/S0012-365X(99)90095-X

[17] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer, New York, 2013). doi:10.1007/978-1-4614-6525-6

[18] C. Lee, The domination number of a tournament, Kangweon-Kyungki Math. J. 9 (2001) 21–28.

[19] R. Molina, On the structure of self-complementary graphs, in: Proc. 25th South-eastern Internat. Conf. on Combinatorics, Graph Theory, Computing (Boca Raton, FL, 7–11 March 1994).

[20] P.S. Nair, Construction of self-complementary graphs, Discrete Math. 175 (1997) 283–287. doi:10.1016/S0012-365X(96)00127-6

[21] P.R.L. Pushpam and C. Suseendran, Further results on secure restrained domination in graphs, J. Discrete Math. Sci. Cryptogr. 19 (2016) 277–291. doi:10.1080/09720529.2014.1001590

[22] Z. Li and J. Xu, A characterization of trees with equal independent domination and secure domination numbers, Inform. Process. Lett. 119 (2017) 14–18. doi:10.1016/j.ipl.2016.11.004

[23] H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962) 270–288.

[24] B. Samadi, H.R. Golmohammadi and A. Khodkar, Bounds on several versions of restrained domination numbers, Contrib. Discrete Math. 12 (2017) 14–19.

[25] S. Skiena, Self-complementary graphs, in: Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (Addison-Wesley, Redwood City, CA, 1990).

[26] J.A. Telle, Vertex Partitioning Problems: Characterization, Complexity and Algorithms on Partial k -Trees, Ph.D. Thesis (University of Oregon, 1994).

[27] J.A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529–550. doi:10.1137/S0895480194275825

[28] W.C.K. Yen, Weighted restrained domination in subclasses of planar graphs, Theoret. Comput. Sci. 630 (2016) 13–25. doi:10.1016/j.tcs.2016.03.022