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

Graphs with Unique Minimum Specified Domination Sets

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

Abstract

In this paper, we consider the graphs that have a unique set that achieves a domination parameter and determine the maximum value of the associated parameter, both in graphs in general and in graphs without end-vertices. For example, for a graph G of order n without an end-vertex, we show an upper bound of n/3 if G has a unique minimum dominating set, an upper bound of \((n-1)/2\) if G has a unique minimum total dominating set or a unique minimum 2-dominating set, and an upper bound of n/2 if G has a unique paired dominating set.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Data Availability

There is no data.

References

  1. Chellali, M., Haynes, T.W.: Trees with unique minimum paired dominating sets. ARS Combin. 73, 3–12 (2004)

    MathSciNet  MATH  Google Scholar 

  2. Chen, L., Lu, C., Zeng, Z.: Graphs with unique minimum paired-dominating set. ARS Combin. 119, 177–192 (2015)

    MathSciNet  MATH  Google Scholar 

  3. Cockayne, E.J., Gamble, B., Shepherd, B.: An upper bound for the \(k\)-domination number of a graph. J. Graph Theory 9, 533–534 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  4. Desormeaux, W.J., Haynes, T.W., Henning, M.A.: Paired domination in graphs. In: Topics in Domination in Graphs, Development in Mathematics, vol. 64, pp. 31–77. Springer, Cham (2020)

    Chapter  MATH  Google Scholar 

  5. Favaron, O.: Two relations between the parameters of independence and irredundance. Discret. Math. 70, 17–20 (1988)

    Article  MathSciNet  Google Scholar 

  6. Fischermann, M.: Unique total domination graphs. ARS Combin. 73, 289–297 (2004)

    MathSciNet  MATH  Google Scholar 

  7. Fischermann, M., Volkmann, L.: Unique minimum domination in trees. Australas. J. Combin. 25, 117–124 (2002)

    MathSciNet  MATH  Google Scholar 

  8. Fischermann, M., Volkmann, L., Zverovich, I.: Unique irredundance, domination, and independent domination in graphs. Discret. Math. 305, 190–200 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gunther, G., Hartnell, B., Markus, L.R., Rall, D.: Graphs with unique minimum dominating sets. Congr. Numer. 101, 55–63 (1994)

    MathSciNet  MATH  Google Scholar 

  10. Hansberg, A., Volkmann, L.: Multiple domination. In: Topics in Domination in Graphs, Development in Mathematics, vol. 64, pp. 151–203. Springer, Cham (2020)

    Chapter  MATH  Google Scholar 

  11. Haynes, T.W., Hedetniemi, S.T., Henning, M.A.: Domination in Graphs: Core Concepts. Springer Monographs in Mathematics. Springer, Cham (2023)

    Book  MATH  Google Scholar 

  12. Haynes, T.W., Henning, M.A.: Trees with unique minimum total dominating sets. Discuss. Math. Graph Theory 22, 233–246 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  13. Haynes, T.W., Henning, M.A.: Unique minimum semipaired dominating sets in trees. Discuss. Math. Graph Theory 43, 35–53 (2023)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hedetniemi, J.: On graphs having a unique minimum independent dominating set. Australas. J. Combin. 68, 357–370 (2017)

    MathSciNet  MATH  Google Scholar 

  15. Lu, Y., Hou, X., Xu, J.-M., Li, N.: Trees with unique minimum \(p\)-dominating sets. Util. Math. 86, 193–205 (2011)

    MathSciNet  MATH  Google Scholar 

Download references

Funding

The authors have not disclosed any funding.

Author information

Authors and Affiliations

  1. School of Mathematical and Statistical Sciences, Clemson University, Clemson, USA

    Wayne Goddard

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

    Wayne Goddard & Michael A. Henning

Authors
  1. Wayne Goddard
    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 Wayne Goddard.

Ethics declarations

Conflict of interest

The authors have not disclosed any competing interests.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Goddard, W., Henning, M.A. Graphs with Unique Minimum Specified Domination Sets. Graphs and Combinatorics 39, 103 (2023). https://doi.org/10.1007/s00373-023-02704-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-023-02704-1

Keywords

Search

Navigation