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

^*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

Abstrakt

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.

Originalsprog	Engelsk
Tidsskrift	Discrete Applied mathematics
Vol/bind	302
Sider (fra-til)	1-7
ISSN	0166-218X
DOI	https://doi.org/10.1016/j.dam.2021.05.033
Status	Udgivet - 30. okt. 2021

Bibliografisk note

Funding Information:
Research supported in part by the University of Johannesburg, South Africa.Research of the second author supported by the Danish research council under grant number DFF-7014-00037B.

Publisher Copyright:
© 2021 Elsevier B.V.

Dokumenter og links

10.1016/j.dam.2021.05.033

Citationsformater

@article{babaf613c429431f99bc74ec8d36709d,

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",

}

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

U2 - 10.1016/j.dam.2021.05.033

DO - 10.1016/j.dam.2021.05.033

M3 - Journal article

AN - SCOPUS:85107736755

VL - 302

SP - 1

EP - 7

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -

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

Abstrakt

Bibliografisk note

Dokumenter og links

Fingeraftryk

Citationsformater