A Classification of Cactus Graphs According to Their Total Domination Number

被引:0
作者
Majid Hajian
Michael A. Henning
Nader Jafari Rad
机构
[1] Shahrood University of Technology,Department of Mathematics
[2] University of Johannesburg,Department of Mathematics and Applied Mathematics
[3] Shahed University,Department of Mathematics
来源
Bulletin of the Malaysian Mathematical Sciences Society | 2020年 / 43卷
关键词
Total dominating sets; Total domination number; Cactus graphs; 05C69;
D O I
暂无
中图分类号
学科分类号
摘要
A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The total domination number, γt(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _t(G)$$\end{document}, is the minimum cardinality of a total dominating set of G. A cactus is a connected graph in which every edge belongs to at most one cycle. Equivalently, a cactus is a connected graph in which every block is an edge or a cycle. Let G be a connected graph of order n≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \ge 2$$\end{document} with k≥0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 0$$\end{document} cycles and ℓ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document} leaves. Recently, the authors have proved that γt(G)≥12(n-ℓ+2)-k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _t(G) \ge \frac{1}{2}(n-\ell +2) - k$$\end{document}. As a consequence of this bound, γt(G)=12(n-ℓ+2+m)-k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _t(G) = \frac{1}{2}(n-\ell +2+m) - k$$\end{document} for some integer m≥0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m \ge 0$$\end{document}. In this paper, we characterize the class of cactus graphs achieving equality in this bound, thereby providing a classification of all cactus graphs according to their total domination number.
引用
收藏
页码:1555 / 1568
页数:13
相关论文
共 10 条
  • [1] Chellali M(2006)A note on the total domination number of a tree J. Comb. Math. Comb. Comput. 58 189-193
  • [2] Haynes TW(2003)Vertices contained in all or in no minimum total dominating set of a tree Discrete Math. 260 37-44
  • [3] Cockayne EJ(2016)Lower bounds on the total domination number of a graph J. Comb. Optim. 31 52-66
  • [4] Henning MA(2018)Essential upper bounds on the total domination number Discrete Appl. Math. 244 103-115
  • [5] Mynhardt CM(2014)A new lower bound for the total domination number in graphs proving a Graffiti conjecture Discrete Appl. Math. 173 45-52
  • [6] Desormeaux WJ(undefined)undefined undefined undefined undefined-undefined
  • [7] Henning MA(undefined)undefined undefined undefined undefined-undefined
  • [8] Henning MA(undefined)undefined undefined undefined undefined-undefined
  • [9] Henning MA(undefined)undefined undefined undefined undefined-undefined
  • [10] Yeo A(undefined)undefined undefined undefined undefined-undefined