Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Paired Domination in Graphs

  • Chapter
  • First Online:
Topics in Domination in Graphs

Part of the book series: Developments in Mathematics ((DEVM,volume 64))

Abstract

A set S of vertices in a graph G is a paired dominating set if every vertex of G is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching (not necessarily as an induced subgraph). The minimum cardinality of a paired dominating set of G is the paired domination number of G. This chapter presents a survey of the major results on paired domination with an emphasis on bounds for the paired domination number.

Research of the second and third authors supported in part by the University of Johannesburg.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 119.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. J. D. Alvarado, S. Dantas, and D. Rautenbach, Perfectly relating the domination, total domination, and paired domination numbers of a graph. Discrete Math.338 (2015), 1424–1431.

    Article  MathSciNet  MATH  Google Scholar 

  2. M. Blidia, M. Chellali, and T. W. Haynes, Characterizations of trees with equal paired and double domination numbers. Discrete Math.306 (2006), 1840–1845.

    Article  MathSciNet  MATH  Google Scholar 

  3. B. Bollobás and E. J. Cockayne, Graph theoretic parameters concerning domination, independence and irredundance. J. Graph Theory3 (1979), 241–250.

    Article  MathSciNet  MATH  Google Scholar 

  4. B. Brešar, P. Dorbec, W. Goddard, B. Hartnell, M. A. Henning, S. Klavžar, and D. F. Rall, Vizing’s conjecture: A survey and recent results. J. Graph Theory69 (2012), 46–76.

    Article  MathSciNet  MATH  Google Scholar 

  5. B. Bres̆ar, S. Klavz̆ar, and D. F. Rall, Dominating direct products of graphs. Discrete Math.307 (2000), 1636–1642.

    Google Scholar 

  6. B. Bres̆ar, M. A. Henning, and D. F. Rall, Paired domination of Cartesian products of graphs. Util. Math.73 (2007), 255–265.

    Google Scholar 

  7. R. C. Brigham, P. Z. Chinn, and R. D. Dutton: Vertex domination-critical graphs. Networks18 (1988), 173–179.

    Article  MathSciNet  MATH  Google Scholar 

  8. M. Chellali and T. W. Haynes, Total and paired domination numbers of a tree. AKCE Int. J. Graphs Comb.1 (2004), 69–75.

    MathSciNet  MATH  Google Scholar 

  9. M. Chellali and T. W. Haynes, On paired and double domination in graphs. Util. Math.67 (2005), 161–171.

    MathSciNet  MATH  Google Scholar 

  10. L. Chen, C. Lu, and Z. Zeng, Labeling algorithms for paired domination problems in block and interval graphs. J. Combin. Optim.19 (2010), 457–470.

    Article  MATH  Google Scholar 

  11. L. Chen, C. Lu, and Z. Zeng, A linear time algorithm for paired domination problem in strongly chordal graphs. Inform. Process. Lett.110 (2009), 20–23.

    Article  MathSciNet  MATH  Google Scholar 

  12. L. Chen, C. Lu, and Z. Zeng, Hardness results and approximation algorithms for (weighted) paired domination in graphs. Theoret. Comput. Sci.410 (2009), no. 47–49, 5063–5071.

    Article  MathSciNet  MATH  Google Scholar 

  13. X. G. Chen, W. C. Shiu, and W. H. Chan, Upper bounds on the paired domination number. Appl. Math. Lett.21 (2008), 1194–1198.

    Article  MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

  15. T. C. E. Cheng, L. Kang, and C. T. Ng, Paired domination on interval and circular-arc graphs. Discrete Appl. Math.155 (2007), 2077–2086.

    Article  MathSciNet  MATH  Google Scholar 

  16. K. Choudhary, S. Margulies, and I. V. Hicks, A note on total and paired domination of Cartesian product graphs. Electron. J. Combin.20 (2013), no. 3, Paper 25, 9 pp.

    Google Scholar 

  17. W. E. Clark, B. Shekhtman, S. Suen, and D. C. Fisher, Upper bounds for the domination number of a graph. Congr. Numer.132 (1998), 99–123.

    MathSciNet  MATH  Google Scholar 

  18. W. E. Clark and S. Suen, An inequality related to Vizing’s conjecture. Electron. J. Combin.7 (2000), no.1, Note 4, 3pp.

    Google Scholar 

  19. J. Cyman, M. Dettlaff, M.A. Henning, M. Lemańska, and J. Raczek, Total domination versus paired-domination in regular graphs. Discuss. Math. Graph Theory38 (2018), 573–586.

    Article  MathSciNet  MATH  Google Scholar 

  20. E. DeLaViña, Q. Liu, R. Pepper, B. Waller, and D. B. West, Some conjectures of Graffiti.pc on total domination. Congr. Numer.185 (2007), 81–95.

    Google Scholar 

  21. N. Dehgardi, S.M. Sheikholeslami, and A. Khodkar, Bounding the paired-domination number of a tree in terms of its annihilation number. Filomat28 (2014), 523–529.

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  23. P. Dorbec and S. Gravier, Paired domination in subdivided star-free graphs. Graphs Combin.26 (2010), 43–49.

    Article  MathSciNet  MATH  Google Scholar 

  24. P. Dorbec and S. Gravier, Paired domination in P 5-free graphs. Graphs Combin.24 (2008), 303–308.

    Article  MathSciNet  MATH  Google Scholar 

  25. P. Dorbec, S. Gravier, and M. A. Henning, Paired domination in generalized claw-free graphs. J. Combin. Optim.14 (2007), 1–7.

    Article  MathSciNet  MATH  Google Scholar 

  26. P. Dorbec, B. Hartnell, and M.A. Henning, Paired versus double domination in K 1,r-free graphs. J. Comb. Optim.27 (2014), 688–694.

    Article  MathSciNet  MATH  Google Scholar 

  27. P. Dorbec and M. A. Henning, Upper paired domination in claw-free graphs. J. Combin. Optim.22 (2011), 235–251.

    Article  MathSciNet  MATH  Google Scholar 

  28. P. Dorbec, M. A. Henning, and J. McCoy, Upper total domination versus upper paired domination.Quaest. Math.30 (2007), 1–12.

    Google Scholar 

  29. M. Edwards, Criticality concepts for paired domination in graphs. MS Thesis. University of Victoria, (2006).

    Google Scholar 

  30. M. Edwards, R. G. Gibson, M. A. Henning, and C. M. Mynhardt, Diameter of paired domination edge-critical graphs. Australas. J. Combin.40 (2008), 279–291.

    MathSciNet  MATH  Google Scholar 

  31. O. Favaron, Bounds on total and paired domination parameters in graphs and claw-free graphs. Erster Aaachner Tag der Graphentheorie, 59–73, Rheinisch-Westfalisch Tech. Hochsch. Lehrstufl II Math Aachen, 2004.

    Google Scholar 

  32. O. Favaron and M. A. Henning, Paired domination in claw-free cubic graphs. Graphs Combin.20 (2004), 447–456.

    Article  MathSciNet  MATH  Google Scholar 

  33. O. Favaron and M. A. Henning, Bounds on total domination in claw-free cubic graphs. Discrete Math.308 (2008), 3491–3507.

    Article  MathSciNet  MATH  Google Scholar 

  34. O. Favaron, H. Karami, and S. M. Sheikholeslami, Paired domination number of a graph and its complement. Discrete Math.308 (2010), 6601–6605.

    Article  MathSciNet  MATH  Google Scholar 

  35. M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to the Theory of NP-Completeness, Freeman, New York, 1979.

    MATH  Google Scholar 

  36. W. Goddard and M. A. Henning, Domination in planar graphs with small diameter. J. Graph Theory40 (2002), 1–25.

    Article  MathSciNet  MATH  Google Scholar 

  37. 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.

    Article  MathSciNet  MATH  Google Scholar 

  38. T. W. Haynes and M. A. Henning, Paired-domination game played in graphs. Commun. Comb. Optim.4 (2019), 79–94.

    MathSciNet  MATH  Google Scholar 

  39. T. W. Haynes and M. A. Henning, Trees with large paired domination number. Util. Math.71 (2006), 3–12.

    MathSciNet  MATH  Google Scholar 

  40. T. W. Haynes, M. A. Henning, and P. J. Slater, Trees with equal domination and paired domination numbers. Ars. Combin.76 (2005), 169–175.

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  42. T. W. Haynes and P. J. Slater, Paired domination in graphs. Networks32 (1998), 199–206.

    Article  MathSciNet  MATH  Google Scholar 

  43. M. A. Henning, Trees with equal total domination and paired domination numbers. Util. Math.69 (2006), 207–218.

    MathSciNet  MATH  Google Scholar 

  44. M. A. Henning, Graphs with large paired domination number. J. Combin. Optim.13 (2007), 61–78.

    Article  MathSciNet  MATH  Google Scholar 

  45. M. A. Henning, An upper bound on the paired domination number in terms of the number of edges in the graph. Discrete Math.310 (2010), 2847–2857.

    Article  MathSciNet  MATH  Google Scholar 

  46. M. A. Henning and J. McCoy, Total domination in planar graphs of diameter two. Discrete Math.309 (2009), 6181–6189.

    Article  MathSciNet  MATH  Google Scholar 

  47. M. A. Henning, J. McCoy and J. Southey, Graphs with maximum size and given paired domination number. Discrete Appl. Math.170 (2014), 72–82.

    Article  MathSciNet  MATH  Google Scholar 

  48. M. A. Henning and C. M. Mynhardt, The diameter of paired domination vertex critical graphs. Czechoslovak Math. J.58(133) (2008), no. 4, 887–897.

    Google Scholar 

  49. M. A. Henning and M. D. Plummer, Vertices contained in all or in no minimum paired dominating set of a tree. J. Combin. Optim.10 (2005), 283–294.

    Article  MathSciNet  MATH  Google Scholar 

  50. M. A. Henning and D. Pradhan, Algorithmic aspects of upper paired-domination in graphs. Theoret. Comput. Sci.804 (2020), 98–114.

    Article  MathSciNet  MATH  Google Scholar 

  51. M. A. Henning and J. Southey, A characterization of graphs of minimum size having diameter two and no dominating vertex, manuscript (2012).

    Google Scholar 

  52. M. A. Henning and P. D. Vestergaard, Trees with paired domination number twice their domination number. Util. Math.74 (2007), 187–197.

    MathSciNet  MATH  Google Scholar 

  53. X. Hou, A characterization of (2γ, γ p)-trees. Discrete Math.308 (2008), 3420–3426.

    Google Scholar 

  54. X. Hou and M. Edwards, Paired domination vertex critical graphs. Graphs Combin.24 (2008), 453–459.

    Article  MathSciNet  MATH  Google Scholar 

  55. X. M. Hou and F. Jiang, Paired domination of Cartesian products of graphs. J. Math. Res. Exposition30 (2010), 181–185.

    MathSciNet  MATH  Google Scholar 

  56. S. Huang and E. Shan, A note on the upper bound for the paired domination number of a graph with minimum degree at least two. Networks57 (2011), 115–116.

    MathSciNet  MATH  Google Scholar 

  57. S. Huang, E. Shan, and L. Kang, Perfect matchings in paired domination vertex critical graphs. J. Combin. Optim.23 (2012), 507–518.

    Article  MathSciNet  MATH  Google Scholar 

  58. S. Huang, L. Kang, and E. Shan, Paired-domination in claw-free graphs. Graphs Combin.29 (2013), 1777–1794.

    Article  MathSciNet  MATH  Google Scholar 

  59. L. Kang, M. Y. Sohn, and T. C. E. Cheng, Paired domination in inflated graphs. Theoret. Comput. Sci.320 (2004), 485–494.

    Article  MathSciNet  MATH  Google Scholar 

  60. E. Lappas, S. D. Nikolopoulos, and L. Palios, An O(n)-time algorithm for the paired domination problem on permutation graphs. European J. Combin.34 (2013), 593–608.

    Article  MathSciNet  MATH  Google Scholar 

  61. C. Lin and H. Tu, A linear-time algorithm for paired-domination on circular-arc graphs. Theoret. Comput. Sci.591 (2015), 99–105.

    Article  MathSciNet  MATH  Google Scholar 

  62. C. Lu, R. Mao, and B. Wang, Paired-domination in claw-free graphs with minimum degree at least four. Ars Combin. 139 (2018), 393–409.

    MathSciNet  MATH  Google Scholar 

  63. C. Lu, B. Wang, K. Wang, and Y. Wu, Paired-domination in claw-free graphs with minimum degree at least three. Discrete Appl. Math.257 (2019), 250–259.

    Article  MathSciNet  MATH  Google Scholar 

  64. C. Lu, C. Wang, and K. Wang, Upper bounds for the paired-domination numbers of graphs. Graphs Combin. 32 (2016), 1489–1494.

    Article  MathSciNet  MATH  Google Scholar 

  65. G. MacGillivray and K. Seyffarth, Domination numbers of planar graphs. J. Graph Theory22 (1996), 213–229.

    Article  MathSciNet  MATH  Google Scholar 

  66. H. Müller and A. Brandstädt, The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, Theor. Comput. Sci.53 (1987), 257–265.

    Article  MathSciNet  MATH  Google Scholar 

  67. C. M. Mynhardt and M. Schurch, Paired domination in prisms of graphs. Discuss. Math. Graph Theory31 (2011), 5–23.

    Article  MathSciNet  MATH  Google Scholar 

  68. B.S. Panda and D. Pradhan, A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph. Discrete Appl. Math.161 (2013), 1776–1783.

    Article  MathSciNet  MATH  Google Scholar 

  69. P. Paulraja and S. Sampathkumar, A note on paired domination number of tensor product of graphs. Bull. Inst. Combin. Appl.60 (2010), 79–85.

    MathSciNet  MATH  Google Scholar 

  70. D. Pradhan and B. S. Panda, Computing a minimum paired-dominating set in strongly orderable graphs. Discrete Appl. Math.253 (2019), 37–50.

    Article  MathSciNet  MATH  Google Scholar 

  71. K. E. Proffit, T. W. Haynes, and P.J. Slater, Paired domination in grid graphs. Congr. Numer.150 (2001), 161–172.

    MathSciNet  MATH  Google Scholar 

  72. H. Qiao, L. Kang, M. Cardel, and D. Z. Du, Paired domination of trees. Dedicated to Professor J.B. Rosen on his 80th birthday. J. Global Optim.25 (2003), 43–54.

    Google Scholar 

  73. J. Raczek, Lower bound on the paired domination number of a tree. Australas. J. Combin.34 (2006), 343–347.

    MathSciNet  MATH  Google Scholar 

  74. O. Schaudt, Paired and induced paired domination in (E, net)-free graphs. Discuss. Math. Graph Theory32 (2012), 473–485.

    Article  MathSciNet  MATH  Google Scholar 

  75. O. Schaudt, Total domination versus paired domination. Discuss. Math. Graph Theory32 (2012), 435–447.

    Article  MathSciNet  MATH  Google Scholar 

  76. E. Shan, L. Kang, and M. A. Henning, A characterization of trees with equal total domination and paired domination numbers. Australas. J. Combin.30 (2004), 31–39.

    MathSciNet  MATH  Google Scholar 

  77. D. S. Studer, T. W. Haynes, and L. M. Lawson, Induced paired domination in graphs. Ars Combin.57 (2000), 111–128.

    MathSciNet  MATH  Google Scholar 

  78. W. Ulatowski, All graphs with paired-domination number two less than their order. Opusc. Math.33 (2013), 763–783.

    Article  MathSciNet  MATH  Google Scholar 

  79. W. Ulatowski, The paired-domination and the upper paired-domination numbers of graphs. Opusc. Math.35 (2015), 127–135.

    Article  MathSciNet  MATH  Google Scholar 

  80. V. G. Vizing, A bound on the external stability number of a graph. Dokl. Akad. Nauk SSSR164 (1965), 729–731.

    MathSciNet  Google Scholar 

  81. V. G. Vizing, Some unsolved problems in graph theory. Uspehi Mat. Nauk23 (1968), (144), 117–134.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Applied Mathematics, University of Johannesburg, 2006, Auckland Park, South Africa

    Wyatt J. Desormeaux, Teresa W. Haynes & Michael A. Henning

  2. Department of Mathematics and Statistics, East Tennessee State University, Johnson City, 37614-0002, TN, USA

    Teresa W. Haynes

Authors
  1. Wyatt J. Desormeaux
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Teresa W. Haynes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael A. Henning
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael A. Henning .

Editor information

Editors and Affiliations

  1. Department of Mathematics and Statistics, East Tennessee State University, Johnson City, TN, USA

    Teresa W. Haynes

  2. School of Computing, Clemson University, Clemson, SC, USA

    Stephen T. Hedetniemi

  3. Department of Mathematics and Applied Mathematics, University of Johannesburg, Johannesburg, South Africa

    Michael A. Henning

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Desormeaux, W.J., Haynes, T.W., Henning, M.A. (2020). Paired Domination in Graphs. In: Haynes, T.W., Hedetniemi, S.T., Henning, M.A. (eds) Topics in Domination in Graphs. Developments in Mathematics, vol 64. Springer, Cham. https://doi.org/10.1007/978-3-030-51117-3_3

Download citation

Publish with us

Policies and ethics

Search

Navigation