Lower bounds on the total domination number of a graph

Wyatt J. Desormeaux; Michael A. Henning

doi:10.1007/s10878-014-9708-2

Lower bounds on the total domination number of a graph

Wyatt J. Desormeaux, Michael A. Henning

Mathematics and Applied Mathematics

University of Johannesburg

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

5 Citations (Scopus)

Abstract

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to a vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Much interest in total domination in graphs has arisen from a computer program Graffiti.pc that has generated several hundred conjectures on total domination (see http://cms.dt.uh.edu/faculty/delavinae/research/wowII). We prove and disprove some conjectures from Graffiti.pc concerning lower bounds on the total domination number of a graph.

Original language	English
Pages (from-to)	52-66
Number of pages	15
Journal	Journal of Combinatorial Optimization
Volume	31
Issue number	1
DOIs	https://doi.org/10.1007/s10878-014-9708-2
Publication status	Published - 1 Jan 2016

Keywords

Graffiti.pc conjectures
Total domination
Total domination number

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10878-014-9708-2

Cite this

@article{d5488e0758d3424f9cf6dd42e17ba710,

title = "Lower bounds on the total domination number of a graph",

abstract = "A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to a vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Much interest in total domination in graphs has arisen from a computer program Graffiti.pc that has generated several hundred conjectures on total domination (see http://cms.dt.uh.edu/faculty/delavinae/research/wowII). We prove and disprove some conjectures from Graffiti.pc concerning lower bounds on the total domination number of a graph.",

keywords = "Graffiti.pc conjectures, Total domination, Total domination number",

author = "Desormeaux, {Wyatt J.} and Henning, {Michael A.}",

note = "Publisher Copyright: {\textcopyright} 2014, Springer Science+Business Media New York.",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/s10878-014-9708-2",

language = "English",

volume = "31",

pages = "52--66",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Lower bounds on the total domination number of a graph

AU - Desormeaux, Wyatt J.

AU - Henning, Michael A.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to a vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Much interest in total domination in graphs has arisen from a computer program Graffiti.pc that has generated several hundred conjectures on total domination (see http://cms.dt.uh.edu/faculty/delavinae/research/wowII). We prove and disprove some conjectures from Graffiti.pc concerning lower bounds on the total domination number of a graph.

AB - A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to a vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Much interest in total domination in graphs has arisen from a computer program Graffiti.pc that has generated several hundred conjectures on total domination (see http://cms.dt.uh.edu/faculty/delavinae/research/wowII). We prove and disprove some conjectures from Graffiti.pc concerning lower bounds on the total domination number of a graph.

KW - Graffiti.pc conjectures

KW - Total domination

KW - Total domination number

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

U2 - 10.1007/s10878-014-9708-2

DO - 10.1007/s10878-014-9708-2

M3 - Article

AN - SCOPUS:84953635233

SN - 1382-6905

VL - 31

SP - 52

EP - 66

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

Lower bounds on the total domination number of a graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this