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

Michael A. Henning; Anders Yeo

doi:10.1016/j.dam.2021.05.033

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

Michael A. Henning, Anders Yeo

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

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 language	English
Pages (from-to)	1-7
Number of pages	7
Journal	Discrete Applied Mathematics
Volume	302
DOIs	https://doi.org/10.1016/j.dam.2021.05.033
Publication status	Published - 30 Oct 2021

Keywords

Hypergraph
Minimum degree six
Total domination in graphs
Transversal

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2021.05.033

Cite this

@article{e93b364a78d1427ab07ef56bab46ccca,

title = "A new upper bound on the total domination number in graphs with minimum degree six",

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{\'e} 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{\'e}–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.",

keywords = "Hypergraph, Minimum degree six, Total domination in graphs, Transversal",

author = "Henning, {Michael A.} and Anders Yeo",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = oct,

day = "30",

doi = "10.1016/j.dam.2021.05.033",

language = "English",

volume = "302",

pages = "1--7",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

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

AU - Henning, Michael A.

AU - Yeo, Anders

PY - 2021/10/30

Y1 - 2021/10/30

N2 - 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.

AB - 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.

KW - Hypergraph

KW - Minimum degree six

KW - Total domination in graphs

KW - Transversal

UR - http://www.scopus.com/inward/record.url?scp=85107736755&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2021.05.033

DO - 10.1016/j.dam.2021.05.033

M3 - Article

AN - SCOPUS:85107736755

SN - 0166-218X

VL - 302

SP - 1

EP - 7

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this