Article,
A new upper bound on the total domination number in graphs with minimum degree six
Contributors
Henning, Michael A
0000-0001-8185-067X
(Corresponding author)
[1]
Yeo, Anders
0000-0003-0293-8708
[1]
[2]
Affiliations
- [1] University of Johannesburg [NORA names: South Africa; Africa];
- [2] University of Southern Denmark [NORA names: SDU University of Southern Denmark; University; Denmark; Europe, EU; Nordic; OECD]
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 γ t ( G ) ≤ 4 11 n . 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 γ t ( G ) ≤ 5138 14145 n < 4 11 − 1 2510 n . This improves the best known upper bounds to date on the total domination number of a graph with minimum degree at least 6.
