Triangles and (Total) Domination in Subcubic Graphs

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₄- 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].