Triangles and (Total) Domination in Subcubic Graphs

Ammar Babikir, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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 K1 , 3 (resp., K4- 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 languageEnglish
Article number28
JournalGraphs and Combinatorics
Issue number2
Publication statusPublished - Apr 2022


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Triangles and (Total) Domination in Subcubic Graphs'. Together they form a unique fingerprint.

Cite this