Skip to main content
Springer Nature Link
Log in

An Improved Upper Bound on the Total Restrained Domination Number in Cubic Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

In this paper, we continue the study of total restrained domination in graphs. A set S of vertices in a graph G = (V, E) is a total restrained dominating set of G if every vertex of G is adjacent to some vertex in S and every vertex of \({V {\setminus} S}\) is adjacent to a vertex in \({V {\setminus} S}\) . The minimum cardinality of a total restrained dominating set of G is the total restrained domination number γ tr(G) of G. Jiang et al. (Graphs Combin 25:341–350, 2009) showed that if G is a connected cubic graph of order n, then γ tr(G) ≤ 13n/19. In this paper we improve this upper bound to γ tr(G) ≤ (n + 4)/2. We provide two infinite families of connected cubic graphs G with γ tr(G) = n/2, showing that our new improved bound is essentially best possible.

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

Access this article

Log in via an institution

Subscribe and save

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

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Archdeacon D., Ellis-Monaghan J., Fischer D., Froncek D., Lam P.C.B., Seager S., Wei B., Yuster R.: Some remarks on domination. J. Graph Theory 46, 207–210 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Chen X.G., Shiu W.C., Chen H.Y.: Trees with equal total domination and total restrained domination numbers. Discuss. Math. Graph Theory 28, 59–66 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  3. Chvátal V., McDiarmid C.: Small transversals in hypergraphs. Combinatorica 12, 19–26 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  4. Favaron O., Henning M.A., Mynhardt C.M., Puech J.: Total domination in graphs with minimum degree three. J. Graph Theory 34, 9–19 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  5. Hattingh J.H., Jonck E., Joubert E.J., Plummer A.R.: Total restrained domination in trees. Discrete Math. 307, 1643–1650 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  6. Hattingh J.H., Jonck E., Joubert E.J., Plummer A.R.: Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs. Discrete Math. 308, 1080–1087 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (eds.): Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)

  8. Henning M.A.: Recent results on total domination in graphs: a survey. Discrete Math. 309, 32–63 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Henning M.A., Maritz J.E.: Total restrained domination in graphs with minimum degree two. Discrete Math. 308, 1909–1920 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Henning M.A., Yeo A.: Total domination in graphs with given girth. Graphs Combin. 24, 333–348 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. Henning M.A., Yeo A.: Hypergraphs with large transversal number and with edge sizes at least three. J. Graph Theory 59, 326–348 (2008)

    MathSciNet  MATH  Google Scholar 

  12. Henning M.A., Yeo A.: Total domination in 2-connected graphs and in graphs with no induced 6-cycles. J. Graph Theory 60, 55–79 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  13. Jiang H., Kang L., Shan E.: Total restrained domination in cubic graphs. Graphs Combin. 25, 341–350 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  14. König, D.: Über Graphen und ihre Anwendung auf Determinantheorie und Mengenlehre. Math. Ann. 77, 453–465 (1916)

    Article  MathSciNet  MATH  Google Scholar 

  15. Ma D.X., Chen X.G., Sun L.: On total restrained domination in graphs. Czechoslov. Math. J. 55, 165–173 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  16. Raczek J., Cyman J.: On the total restrained domination number of a graph. Australas. J. Combin. 36, 91–100 (2006)

    MathSciNet  MATH  Google Scholar 

  17. Raczek J., Cyman J.: Total restrained domination numbers of trees. Discrete Math. 308, 44–50 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  18. Telle J., Proskurowski A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math. 10, 529–550 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  19. Thomassé S., Yeo A.: Total domination of graphs and small transversals of hypergraphs. Combinatorica 27, 473–487 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  20. Tuza Z.: Covering all cliques of a graph. Discrete Math. 86, 117–126 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  21. Zelinka B.: Remarks on restrained domination and total restrained domination in graphs. Czechoslov. Math. J. 55, 393–396 (2005)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Justin Southey & Michael A. Henning

Authors
  1. Justin Southey
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael A. Henning
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Justin Southey.

Additional information

J. Southey research was supported in part by the South African National Research Foundation. M.A. Henning research was supported in part by the South African National Research Foundation and the University of Johannesburg.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Southey, J., Henning, M.A. An Improved Upper Bound on the Total Restrained Domination Number in Cubic Graphs. Graphs and Combinatorics 28, 547–554 (2012). https://doi.org/10.1007/s00373-011-1059-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-011-1059-5

Keywords

Mathematics Subject Classification (2000)

Search

Navigation