Domination versus total domination in claw-free cubic graphs

Ammar Babikir, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

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 languageEnglish
Article number112784
JournalDiscrete Mathematics
Volume345
Issue number4
DOIs
Publication statusPublished - Apr 2022

Keywords

  • Claw-free
  • Cubic
  • Domination
  • Total domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Domination versus total domination in claw-free cubic graphs'. Together they form a unique fingerprint.

Cite this