[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Characterization of Graphs with Semitotal Domination Number One-Third Their Order

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

Abstract

In an isolate-free graph G, a subset S of vertices is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number of G, denoted by \(\gamma _{t2}(G)\), is the minimum cardinality of a semitotal dominating set in G. Zhu et al. (Gr Combin 33, 1119–1130, 2017) proved that if \(G\notin \{K_4,N_2\}\) is a connected claw-free cubic graph of order n, then \(\gamma _{t2}(G)\le \frac{n}{3}\), which is sharp. They proposed the problem of characterizing the extremal graphs. We completely solve this problem. There are ten classes of graphs, three of which are infinite families of graphs.

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
£29.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 includes VAT (United Kingdom)

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

Not applicable.

Code Availability

Not applicable.

References

  1. Chen, J., Xu, S.-J.: A characterization of 3-\(\gamma \)-critical graphs which are not bicritical. Inf. Process. Lett. 166, 106062 (2021)

    Article  MathSciNet  Google Scholar 

  2. Dong, Y.X., Shan, E.F., Kang, L.Y., Li, S.: Domination in intersecting hypergraphs. Discrete Appl. Math. 251, 155–159 (2018)

    Article  MathSciNet  Google Scholar 

  3. Favaron, O., Henning, M.A.: Paired-domination in claw-free cubic graphs. Gr. Combin. 20(4), 447–456 (2004)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  5. Goddard, W., Henning, M.A., McPillan, C.A.: Semitotal domination in graphs. Util. Math. 94, 67–81 (2014)

    MathSciNet  Google Scholar 

  6. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Maecel Dekker Inc., New York (1998)

    Google Scholar 

  7. Henning, M.A.: Edge weighting functions on semitotal dominating sets. Gr. Combin. 33, 403–417 (2017)

    Article  MathSciNet  Google Scholar 

  8. Henning, M.A.: Bounds on domination parameters in graphs: a brief survey. Discuss. Math. Gr. Theory 42, 665–708 (2022)

    Article  MathSciNet  Google Scholar 

  9. Henning, M.A., Löwenstein, C.: Locating-total domination in claw-free cubic graphs. Discrete Math. 312, 3107–3116 (2012)

    Article  MathSciNet  Google Scholar 

  10. Henning, M.A., Marcon, A.J.: On matching and semitotal domination in graphs. Discrete Math. 324, 13–18 (2014)

    Article  MathSciNet  Google Scholar 

  11. Henning, M.A., Marcon, A.J.: Semitotal domination in claw-free cubic graphs. Ann. Comb. 20(4), 1–15 (2016)

    Article  MathSciNet  Google Scholar 

  12. Henning, M.A., Pandey, A.: Algorithmic aspects of semitotal domination in graphs. Theoret. Comput. Sci. 766, 46–57 (2019)

    Article  MathSciNet  Google Scholar 

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

    Book  Google Scholar 

  14. Henning, M.A., Kang, L., Shan, E., Yeo, A.: On matching and total domination in graphs. Discrete Math. 308, 2313–2318 (2008)

    Article  MathSciNet  Google Scholar 

  15. Southey, J., Henning, M.A.: On a conjecture on total domination in claw-free cubic graphs. Discrete Math. 310(21), 2984–2999 (2010)

    Article  MathSciNet  Google Scholar 

  16. Zhu, E., Liu, C.: On the semitotal domination number of line graphs. Discrete Appl. Math. 254, 295–298 (2019)

    Article  MathSciNet  Google Scholar 

  17. Zhu, E., Shao, Z., Xu, J.: Semitotal domination in claw-free cubic graphs. Gr. Combin. 33(5), 1119–1130 (2017)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to express their gratitude to the referees for their valuable remarks and suggestions which improved the paper.

Funding

This work was funded in part by National Natural Science Foundation of China (Grants no. 12071194).

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Gansu Center for Applied Mathematics, Lanzhou University, Lanzhou, 730000, Gansu, China

    Jie Chen, Cai-Xia Wang & Shou-Jun Xu

  2. College of Software, Henan Normal University, Xinxiang, 453000, Henan, China

    Yi-Ping Liang

  3. School of Mathematics and Statistics, Minnan Normal University, Zhangzhou, Fujian, 363000, China

    Shou-Jun Xu

Authors
  1. Jie Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cai-Xia Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yi-Ping Liang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shou-Jun Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed to this paper.

Corresponding author

Correspondence to Shou-Jun Xu.

Ethics declarations

Conflict of interest

The authors declare that they have no Conflict of interest.

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

Chen, J., Wang, CX., Liang, YP. et al. A Characterization of Graphs with Semitotal Domination Number One-Third Their Order. Graphs and Combinatorics 40, 73 (2024). https://doi.org/10.1007/s00373-024-02800-w

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-024-02800-w

Keywords

Mathematics Subject Classification

Search

Navigation