Semitotal Domination in Claw-Free Cubic Graphs

Michael A. Henning, Alister J. Marcon

Research output: Contribution to journalArticlepeer-review

34 Citations (Scopus)

Abstract

In this paper, we continue the study of semitotal domination in graphs in [Discrete Math. 324, 13–18 (2014)]. A set S of vertices in G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt 2(G) , is the minimum cardinality of a semitotal dominating set of G. This domination parameter is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G) , and the total domination number, γt(G). We observe that γ(G) ≤ γt 2(G) ≤ γt(G). A claw-free graph is a graph that does not contain K1,3 as an induced subgraph. We prove that if G is a connected, claw-free, cubic graph of order n≥ 10 , then γt 2(G) ≤ 4 n/ 11.

Original languageEnglish
Pages (from-to)799-813
Number of pages15
JournalAnnals of Combinatorics
Volume20
Issue number4
DOIs
Publication statusPublished - 1 Dec 2016

Keywords

  • claw-free
  • cubic
  • semitotal domination
  • total domination

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Semitotal Domination in Claw-Free Cubic Graphs'. Together they form a unique fingerprint.

Cite this