Abstract
A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some other vertex in S. A total dominating set S is minimal if no proper subset of S is a total dominating set of G. The upper total domination number, Γ t(G) , of G is the maximum cardinality of a minimal total dominating set of G. A claw-free graph is a graph that does not contain a claw K1 , 3 as an induced subgraph. It is known, or can be readily deduced, that if G≠ K4 is a connected claw-free cubic graph of order n, then 13n≤α(G)≤25n, and 13n≤Γ(G)≤12n, and these bounds are tight, where α(G) and Γ (G) denote the independence number and upper domination number, respectively, of G. In this paper, we prove that if G is a connected claw-free cubic graph of order n, then 49n≤Γt(G)≤35n.
Original language | English |
---|---|
Article number | 172 |
Journal | Graphs and Combinatorics |
Volume | 38 |
Issue number | 6 |
DOIs | |
Publication status | Published - Dec 2022 |
Keywords
- Claw-free cubic graph
- Total domination
- Upper total domination
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics