Upper Total Domination in Claw-Free Cubic Graphs

Ammar Babikir, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

Abstract

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some other vertex in S. A total dominating set S is minimal if no proper subset of S is a total dominating set of G. The upper total domination number, Γ t(G) , of G is the maximum cardinality of a minimal total dominating set of G. A claw-free graph is a graph that does not contain a claw K1 , 3 as an induced subgraph. It is known, or can be readily deduced, that if G≠ K4 is a connected claw-free cubic graph of order n, then 13n≤α(G)≤25n, and 13n≤Γ(G)≤12n, and these bounds are tight, where α(G) and Γ (G) denote the independence number and upper domination number, respectively, of G. In this paper, we prove that if G is a connected claw-free cubic graph of order n, then 49n≤Γt(G)≤35n.

Original languageEnglish
Article number172
JournalGraphs and Combinatorics
Volume38
Issue number6
DOIs
Publication statusPublished - Dec 2022

Keywords

  • Claw-free cubic graph
  • Total domination
  • Upper total domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

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

Cite this