Abstract
A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, every vertex in S is adjacent to some other vertex in S, then S is a total dominating set. The domination number γ(G) of G is the minimum cardinality of a dominating set in G, while the total domination number γt(G) of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain K1,3 as an induced subgraph. Let G be a connected, claw-free, cubic graph of order n. We show that if we exclude two graphs, then [Formula presented], and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then [Formula presented], and this bound is best possible. These bounds improve previously best known results due to Favaron and Henning (2008) [7], Southey and Henning (2010) [19].
Original language | English |
---|---|
Article number | 112784 |
Journal | Discrete Mathematics |
Volume | 345 |
Issue number | 4 |
DOIs | |
Publication status | Published - Apr 2022 |
Keywords
- Claw-free
- Cubic
- Domination
- Total domination
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics