PDF

Discussiones Mathematicae Graph Theory 32(3) (2012) 435-447
DOI: https://doi.org/10.7151/dmgt.1614

Total Domination Versus Paired
Domination

Oliver Schaudt Institut für Informatik Universität zu Köln Weyertal 80, 50931 Cologne, Germany

Abstract

A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by γ_t. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γ_t. A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by γ_p. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γ_p.

In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γ_p/ γ_t ≤ 2 − 2/r for K_1,r-free graphs. As a consequence, we obtain the sharp bound γ_p/ γ_t ≤ 2 − 2/( Δ+1), where Δ is the maximum degree. We also show for each r ≥ 2 that {C₅,T_r}-free graphs fulfill the sharp bound γ_p/ γ_t ≤ 2 − 2/r, where T_r is obtained from K_1,r by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Γ_p / Γ_t. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γ_p ≤ Γ_t holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio γ_p / Γ_t taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γ_p/ Γ_t ≤ 2 − 2/r for graphs that do not contain the corona of K_1,r as subgraph. In particular, we obtain the sharp bound γ_p/ Γ_t ≤ 2 − 2/ Δ.

Keywords: total domination, upper total domination, paired domination, upper paired domination, generalized claw-free graphs

2010 Mathematics Subject Classification: 05C69.

References

[1]	T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, (Marcel Dekker, New York, 1998).
[2]	E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211--219, doi: 10.1002/net.3230100304.
[3]	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.
[4]	T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199--206, doi: 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F.
[5]	J.A. Telle, Complexity of domination-type problems in graphs, Nordic J. Comput. 1 (1994) 157--171.
[6]	T.W. Haynes, L.M. Lawson and D.S. Studer, Induced-paired domination in graphs, Ars Combin. 57 (2000) 111--128.
[7]	B. Zelinka, Induced-paired domatic numbers of graphs, Math. Bohem. 127 (2002) 591--596.
[8]	O. Favaron and M.A. Henning, Total domination in claw-free graphs with minimum degree 2, Discrete Math. 308 (2008) 3213--3219, doi: 10.1016/j.disc.2007.06.024.
[9]	O. Favaron and M.A. Henning, Bounds on total domination in claw-free cubic graphs, Discrete Math. 308 (2008) 3491--3507, doi: 10.1016/j.disc.2007.07.007.
[10]	O. Favaron and M.A. Henning, Upper total domination in claw-free graphs, J. Graph Theory 44 (2003) 148--158, doi: 10.1002/jgt.10134.
[11]	M.A. Henning and J. Southey, On a conjecture on total domination in claw-free cubic graphs, Discrete Math. 310 (2010) 2984--2999, doi: 10.1016/j.disc.2010.07.006.
[12]	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.
[13]	P. Dorbec and S. Gravier, Paired-domination in subdivided star-free graphs, Graphs Combin. 26 (2010) 43--49, doi: 10.1007/s00373-010-0893-1.
[14]	M. Blidia, M. Chellali and O. Favaron, Ratios of Some Domination Parameters in Graphs and Claw-free Graphs, In: A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier and J.L. Ramírez Alfonsín (Eds.), Trends in Mathematics: Graph Theory in Paris, Birkhäuser, Basel, (2007) 61–72, doi: 10.1007/978-3-7643-7400-6_6.
[15]	R.C. Brigham and R.D. Dutton, Domination in claw-free graphs, Congr. Numer. 132 (1998) 69--75.
[16]	P. Dorbec, M.A. Henning and J. McCoy, Upper total domination versus upper paired-domination, Quaest. Math. 30 (2007) 1--12, doi: 10.2989/160736007780205693.
[17]	O. Schaudt, On the existence of total dominating subgraphs with a prescribed additive hereditary property, Discrete Math. 311 (2011) 2095--2101, doi: 10.1016/j.disc.2011.05.036.
[18]	C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences of the United States of America 43 (1957) 842--844, doi: 10.1073/pnas.43.9.842.
[19]	M.D. Plummer and A. Saito, Forbidden subgraphs and bounds on the size of a maximum matching, J. Graph Theory 50 (2005) 1--12, doi: 10.1002/jgt.20087.

Received 28 February 2011
Accepted 3 August 2011