Discussiones Mathematicae Graph Theory 32(3) (2012)
435-447

doi: 10.7151/dmgt.1614

Domination

Oliver Schaudt
Institut für Informatik |

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_{5},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.

[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 , Discrete Math. 2 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