Total domination versus paired domination

Oliver Schaudt

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 3, page 435-447
  • ISSN: 2083-5892

Abstract

top
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 γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. 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 γₚ. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γₚ. In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γₚ/γₜ ≤ 2 - 2/r for K 1 , r -free graphs. As a consequence, we obtain the sharp bound γₚ/γₜ ≤ 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 γₚ/γₜ ≤ 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 Γₚ/Γₜ. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γₚ ≤ Γₜ 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 γₚ/Γₜ taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γₚ/Γₜ ≤ 2 - 2/r for graphs that do not contain the corona of K 1 , r as subgraph. In particular, we obtain the sharp bound γₚ/Γₜ ≤ 2 - 2/Δ.

How to cite

top

Oliver Schaudt. "Total domination versus paired domination." Discussiones Mathematicae Graph Theory 32.3 (2012): 435-447. <http://eudml.org/doc/270836>.

@article{OliverSchaudt2012,
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 γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. 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 γₚ. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γₚ. In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γₚ/γₜ ≤ 2 - 2/r for $K_\{1,r\}$-free graphs. As a consequence, we obtain the sharp bound γₚ/γₜ ≤ 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 γₚ/γₜ ≤ 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 Γₚ/Γₜ. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γₚ ≤ Γₜ 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 γₚ/Γₜ taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γₚ/Γₜ ≤ 2 - 2/r for graphs that do not contain the corona of $K_\{1,r\}$ as subgraph. In particular, we obtain the sharp bound γₚ/Γₜ ≤ 2 - 2/Δ.},
author = {Oliver Schaudt},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {total domination; upper total domination; paired domination; upper paired domination; generalized claw-free graphs},
language = {eng},
number = {3},
pages = {435-447},
title = {Total domination versus paired domination},
url = {http://eudml.org/doc/270836},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Oliver Schaudt
TI - Total domination versus paired domination
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 3
SP - 435
EP - 447
AB - 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 γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. 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 γₚ. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γₚ. In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γₚ/γₜ ≤ 2 - 2/r for $K_{1,r}$-free graphs. As a consequence, we obtain the sharp bound γₚ/γₜ ≤ 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 γₚ/γₜ ≤ 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 Γₚ/Γₜ. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γₚ ≤ Γₜ 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 γₚ/Γₜ taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γₚ/Γₜ ≤ 2 - 2/r for graphs that do not contain the corona of $K_{1,r}$ as subgraph. In particular, we obtain the sharp bound γₚ/Γₜ ≤ 2 - 2/Δ.
LA - eng
KW - total domination; upper total domination; paired domination; upper paired domination; generalized claw-free graphs
UR - http://eudml.org/doc/270836
ER -

References

top
  1. [1] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, (Marcel Dekker, New York, 1998). Zbl0890.05002
  2. [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. Zbl0447.05039
  3. [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. Zbl1219.05121
  4. [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 Zbl0997.05074
  5. [5] J.A. Telle, Complexity of domination-type problems in graphs, Nordic J. Comput. 1 (1994) 157-171. 
  6. [6] T.W. Haynes, L.M. Lawson and D.S. Studer, Induced-paired domination in graphs, Ars Combin. 57 (2000) 111-128. Zbl1064.05115
  7. [7] B. Zelinka, Induced-paired domatic numbers of graphs, Math. Bohem. 127 (2002) 591-596. Zbl1003.05078
  8. [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. Zbl1158.05044
  9. [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. Zbl1190.05089
  10. [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. Zbl1028.05078
  11. [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. Zbl1222.05203
  12. [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. Zbl1125.05072
  13. [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. Zbl1231.05199
  14. [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₆. 
  15. [15] R.C. Brigham and R.D. Dutton, Domination in claw-free graphs, Congr. Numer. 132 (1998) 69-75. Zbl0951.05078
  16. [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. Zbl1134.05071
  17. [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. Zbl1230.05227
  18. [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. Zbl0086.16202
  19. [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. Zbl1070.05070

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.