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

Graphs with Diameter 2 and Large Total Domination Number

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

Abstract

In this paper we show that for each sufficiently large n there exist graphs G of order n and diameter 2 whose total domination number \(\gamma _t(G)\) is greater than \(\sqrt{(3n\log n)/8}-\sqrt{n}\). On the other hand, it is shown that the total domination number of a graph of order \(n \geqslant 3\) and diameter 2 is always less than \(\sqrt{(n\log n)/2}+\sqrt{n/2}\).

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
$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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Akhbari, M.H., Rad, N.J.: Bounds on weak and strong total domination number in graphs. Electron. J. Graph Theory Appl. (EJGTA) 4, 111–118 (2016)

    Article  MathSciNet  Google Scholar 

  2. Bermudo, S., Sanchéz, J.L., Sigaretta, J.M.: Total \(k\)-domination in Cartesian product graphs. Period. Math. Hung. 75, 255–267 (2017)

    Article  MathSciNet  Google Scholar 

  3. Chen, X.-G., Gao, T.: A note on \(\alpha \)-total domination in cubic graphs. Discrete Appl. Math. 217, 718–721 (2017)

    Article  MathSciNet  Google Scholar 

  4. Cockayne, E.J., Dawes, R.M., Hedetniemi, S.T.: Total domination in graphs. Networks 10, 211–219 (1980)

    Article  MathSciNet  Google Scholar 

  5. Desormeaux, W.J., Haynes, T.W., Henning, M.A., Yeo, A.: Total domination in graphs with diameter \(2\). J. Graph Theory 75, 91–103 (2014)

    Article  MathSciNet  Google Scholar 

  6. Desormeaux, W.J., Gibson, P.E., Haynes, T.W.: Bounds on the global domination number. Quaest. Math. 38, 563–572 (2015)

    Article  MathSciNet  Google Scholar 

  7. Duginov, O.: Secure total domination in graphs: bounds and complexity. Discrete Appl. Math. 222, 97–108 (2017)

    Article  MathSciNet  Google Scholar 

  8. Glebov, R., Liebenau, A., Szabó, T.: On the concentration of the domination number of the random graph. SIAM J. Discrete Math. 29, 1186–1206 (2015)

    Article  MathSciNet  Google Scholar 

  9. Henning, M.A., Rad, N.J.: On \(\alpha \)-total domination in graphs. Discrete. Appl. Math. 160, 1143–1151 (2012)

    Article  MathSciNet  Google Scholar 

  10. Henning, M.A., Yeo, A.: A transition from total domination in graphs to transversals in hypergraphs. Quaest. Math. 30, 417–436 (2007)

    Article  MathSciNet  Google Scholar 

  11. Henning, M.A., Yeo, A.: The domination number of a random graph. Util. Math. 94, 315–328 (2014)

    MathSciNet  MATH  Google Scholar 

  12. Henning, M.A., Yeo, A.: Total Domination in Graphs. Springer, New York (2013)

    Book  Google Scholar 

  13. Klostermeyer, W.F., Mynhardt, C.M.: Secure domination and secure total domination in graphs. Discuss. Math. Graph Theory 28, 267–284 (2008)

    Article  MathSciNet  Google Scholar 

  14. Roushini Leely Pushpam, P., Shanthi, P.A.: \(m\)-Eternal total domination in graphs. Discrete Math. Algorithms Appl. 8(3), 1650055 (2016)

    Article  MathSciNet  Google Scholar 

  15. Volkmann, L.: Signed total Roman domination in graphs. J. Comb. Optim. 32, 855–871 (2016)

    Article  MathSciNet  Google Scholar 

  16. Wieland, B., Godbole, A.: On the domination number of a random graph. Electron. J. Combin. 8, 13 (2001)

    Article  MathSciNet  Google Scholar 

  17. Yi, E.: Disjunctive total domination in permutation graphs. Discrete Math. Algorithms Appl. 9(1), 1750009 (2017)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

I thank the referees for suggesting some improvements.

Author information

Authors and Affiliations

  1. Institute of Mathematics, Faculty of Mathematics and Informatics, Vilnius University, Naugarduko 24, 03225, Vilnius, Lithuania

    Artūras Dubickas

Authors
  1. Artūras Dubickas
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Artūras Dubickas.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dubickas, A. Graphs with Diameter 2 and Large Total Domination Number. Graphs and Combinatorics 37, 271–279 (2021). https://doi.org/10.1007/s00373-020-02245-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-020-02245-x

Keywords

Mathematics Subject Classification

Search

Navigation