TY - JOUR

T1 - A Classification of Cactus Graphs According to Their Total Domination Number

AU - Hajian, Majid

AU - Henning, Michael A.

AU - Rad, Nader Jafari

N1 - Publisher Copyright:
© 2019, Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia.

PY - 2020/3/1

Y1 - 2020/3/1

N2 - 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) , 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 with k≥ 0 cycles and ℓ leaves. Recently, the authors have proved that γt(G)≥12(n-ℓ+2)-k. As a consequence of this bound, γt(G)=12(n-ℓ+2+m)-k for some integer m≥ 0. 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.

AB - 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) , 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 with k≥ 0 cycles and ℓ leaves. Recently, the authors have proved that γt(G)≥12(n-ℓ+2)-k. As a consequence of this bound, γt(G)=12(n-ℓ+2+m)-k for some integer m≥ 0. 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.

KW - Cactus graphs

KW - Total dominating sets

KW - Total domination number

UR - http://www.scopus.com/inward/record.url?scp=85079120407&partnerID=8YFLogxK

U2 - 10.1007/s40840-019-00758-0

DO - 10.1007/s40840-019-00758-0

M3 - Article

AN - SCOPUS:85079120407

SN - 0126-6705

VL - 43

SP - 1555

EP - 1568

JO - Bulletin of the Malaysian Mathematical Sciences Society

JF - Bulletin of the Malaysian Mathematical Sciences Society

IS - 2

ER -