A new upper bound on the total domination number in graphs with minimum degree six

Michael A. Henning*, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

A total dominating set in a graph G is a set of vertices of G such that every vertex is adjacent to a vertex of the set. The total domination number γt(G) is the minimum cardinality of a dominating set in G. Thomassé and Yeo (2007) conjectured that if G is a graph on n vertices with minimum degree at least 5, then [Formula presented]. In this paper, it is shown that the Thomassé–Yeo conjecture holds with strict inequality if the minimum degree at least 6. More precisely, it is proven that if G is a graph of order n with δ(G)≥6, then [Formula presented]. This improves the best known upper bounds to date on the total domination number of a graph with minimum degree at least 6.

Original languageEnglish
JournalDiscrete Applied mathematics
Volume302
Pages (from-to)1-7
ISSN0166-218X
DOIs
Publication statusPublished - 30. Oct 2021

Bibliographical note

Publisher Copyright:
© 2021 Elsevier B.V.

Keywords

  • Hypergraph
  • Minimum degree six
  • Total domination in graphs
  • Transversal

Fingerprint

Dive into the research topics of 'A new upper bound on the total domination number in graphs with minimum degree six'. Together they form a unique fingerprint.

Cite this