Geodesic
Total Domination Versus Paired-Domination in Regular Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 573-586.

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

A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the minimum cardinalities of a total dominating set and paired-dominating set are the total domination number, γt(G), and the paired-domination number, γpr(G), respectively. For k ≥ 2, let G be a connected k-regular graph. It is known [Schaudt, Total domination versus paired domination, Discuss. Math. Graph Theory 32 (2012) 435–447] that γpr(G)/γt(G) ≤ (2k)/(k+1). In the special case when k = 2, we observe that γpr(G)/γt(G) ≤ 4/3, with equality if and only if G ≅ C5. When k = 3, we show that γpr(G)/γt(G) ≤ 3/2, with equality if and only if G is the Petersen graph. More generally for k ≥ 2, if G has girth at least 5 and satisfies γpr(G)/γt(G) = (2k)/(k + 1), then we show that G is a diameter-2 Moore graph. As a consequence of this result, we prove that for k ≥ 2 and k ≠ 57, if G has girth at least 5, then γpr(G)/γt(G) ≤ (2k)/(k +1), with equality if and only if k = 2 and G ≅ C5 or k = 3 and G is the Petersen graph.
Keywords: domination, total domination, paired-domination 
@article{DMGT_2018_38_2_a16,
     author = {Cyman, Joanna and Dettlaff, Magda and Henning, Michael A. and Lema\'nska, Magdalena and Raczek, Joanna},
     title = {Total {Domination} {Versus} {Paired-Domination} in {Regular} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {573--586},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a16/}
}
TY  - JOUR
AU  - Cyman, Joanna
AU  - Dettlaff, Magda
AU  - Henning, Michael A.
AU  - Lemańska, Magdalena
AU  - Raczek, Joanna
TI  - Total Domination Versus Paired-Domination in Regular Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 573
EP  - 586
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a16/
LA  - en
ID  - DMGT_2018_38_2_a16
ER  - 
%0 Journal Article
%A Cyman, Joanna
%A Dettlaff, Magda
%A Henning, Michael A.
%A Lemańska, Magdalena
%A Raczek, Joanna
%T Total Domination Versus Paired-Domination in Regular Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 573-586
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a16/
%G en
%F DMGT_2018_38_2_a16
Cyman, Joanna; Dettlaff, Magda; Henning, Michael A.; Lemańska, Magdalena; Raczek, Joanna. Total Domination Versus Paired-Domination in Regular Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 573-586. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a16/

[1] M. Blidia, M. Chellali and T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, Discrete Math. 306 (2006) 1840–1845. doi:10.1016/j.disc.2006.03.061

[2] B. Brešar, M.A. Henning and D.F. Rall, Paired-domination of Cartesian products of graphs, Util. Math. 73 (2007) 255–265.

[3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North Holland, New York, 1976).

[4] X.-G. Chen, L. Sun and H.-M. Xing, Paired-domination numbers of cubic graphs, Acta Math. Sci. Ser. A Chin. Ed. 27 (2007) 166–170, in Chinese.

[5] T.C.E. Cheng, L.Y. Kang and C.T. Ng, Paired domination on interval and circular-arc graphs, Discrete Appl. Math. 155 (2007) 2077–2086. doi:10.1016/j.dam.2007.05.011

[6] T.C.E. Cheng, L.Y. Kang and E. Shan, A polynomial-time algorithm for the paired-domination problem on permutation graphs, Discrete Appl. Math. 157 (2009) 262–271. doi:10.1016/j.dam.2008.02.015

[7] W.J. Desormeaux, T.W. Haynes, M.A. Henning and A. Yeo, Total domination in graphs with diameter 2, J. Graph Theory 75 (2014) 91–103. doi:10.1002/jgt.21725

[8] W.J. Desormeaux and M.A. Henning, Paired domination in graphs: a survey and recent results, Util. Math. 94 (2014) 101–166.

[9] P. Dorbec and S. Gravier, Paired-domination in P5-free graphs, Graphs Combin. 24 (2008) 303–308. doi:10.1007/s00373-008-0792-x

[10] P. Dorbec, S. Gravier and M.A. Henning, Paired-domination in generalized claw-free graphs, J. Comb. Optim. 14 (2007) 1–7. doi:10.1007/s10878-006-9022-8

[11] P. Dorbec, B. Hartnell and M.A. Henning, Paired versus double domination in K1,r-free graphs, J. Comb. Optim. 27 (2014) 688–694. doi:10.1007/s10878-012-9547-y

[12] O. Favaron and M.A. Henning, Paired-domination in claw-free cubic graphs, Graphs Combin. 20 (2004) 447–456. doi:10.1007/s00373-004-0577-9

[13] W. Goddard, personal communication at 16th CID Workshop on Graph Theory, September 20–25 (2015) Szklarska Porȩba, Poland.

[14] W. Goddard and M.A. Henning, A characterization of cubic graphs with paired-domination number three-fifths their order, Graphs Combin. 25 (2009) 675–692. doi:10.1007/s00373-010-0884-2

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

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

[17] T.W. Haynes and P.J. Slater, Paired-domination and the paired-domatic number, Congr. Numer. 109 (1995) 65–72.

[18] T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199–206. doi:10.1002/(SICI)1097-0037(199810)32:3h199::AID-NET4i3.0.CO;2-F

[19] M.A. Henning, Graphs with large paired-domination number, J. Comb. Optim. 13 (2007) 61–78. doi:10.1007/s10878-006-9014-8

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

[21] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, Springer-Verlag, New York, 2013).

[22] A.J. Hoffman and R.R. Singleton, On Moore graphs with diameter 2 and 3, IBM J. Res. Dev. 4 (1960) 497–504. doi:10.1147/rd.45.0497

[23] O. Schaudt, Total domination versus paired domination, Discuss. Math. Graph Theory 32 (2012) 435–447. doi:10.7151/dmgt.1614

[24] N. Robertson, Graphs Minimal Under Girth, Valency, and Connectivity Constraints (Dissertation, Waterloo, Ontario, University of Waterloo, 1969).

[25] R.R. Singleton, There is no irregular Moore graph, Amer. Math. Monthly 75 (1968) 42–43. doi:10.2307/2315106