## 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 a total dominating set in G. The matching number α^{′}(G) is the cardinality of a maximum matching in G. A claw-free (resp., diamond-free) graph is a graph that does not contain K_{1 , 3} (resp., K_{4}- e) as an induced subgraph. We characterize the connected claw-free cubic graphs with maximum possible domination number. We prove that if G is a connected graph of order n with minimum degree δ(G) = 2 and maximum degree Δ (G) = 3 , then α′(G)≥25n, and we characterize the (infinite) family of extremal graphs. Using this matching result, we prove that if G is a diamond-free special subcubic graph of order n, then γt(G)≤25n, where a special subcubic graph is a graph G with 2 ≤ δ(G) and Δ (G) = 3 that satisfies the property that (i) every vertex of G belongs to a triangle and (ii) every triangle contains at most one vertex of degree 2 in G. This result generalizes known results [Graphs Combin. 20 (2004), 447–456].

Original language | English |
---|---|

Article number | 28 |

Journal | Graphs and Combinatorics |

Volume | 38 |

Issue number | 2 |

DOIs | |

Publication status | Published - Apr 2022 |

## Keywords

- Claw-free
- Domination
- Subcubic graph
- Total domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics