A new lower bound for the total domination number in graphs proving a Graffiti.pc Conjecture

Michael A. Henning*, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The total domination number γt(G) of a graph G is the minimum cardinality of a set S of vertices so that every vertex of G is adjacent to a vertex in S. Our main result of this paper is that if G is a connected graph and x1,x2,x3∈V(G), then γt (G)≥1/4(d(x1,x2)+d(x 1,x3)+d(x2,x3)). Furthermore if equality holds in this bound, then the multiset {d(x1,x 2),d(x1,x3),d(x2,x3)} is equal to {2,3,3} modulo four. As a consequence of this result, we prove a conjecture on the total domination number. To state this conjecture, let B denote the set of vertices of maximum eccentricity in G and let ecc(B) denote the maximum distance in G of a vertex outside B to a vertex of B. The following conjecture is known as Graffiti.pc Conjecture #233 (http://cms.dt.uh.edu/ faculty/delavinae/research/wowII): if G is a connected graph of order at least two, then γt(G)≥2(ecc(B)+1)/3. We prove this conjecture. In fact, as a consequence of our main result stated earlier we prove the following much stronger result: if G is a connected graph of order at least two, then γt(G)≥(3ecc(B)+2)/4. We also prove that if G is a connected graph and x1,x2,x3,x4∈V(G), then γt (G)≥1/8(d(x1,x2)+d(x 1,x3)+d(x1,x4)+d(x 2,x3)+d(x2,x4)+d(x 3,x4)), and this result is best possible.

Original languageEnglish
JournalDiscrete Applied Mathematics
Volume173
Issue number20
Pages (from-to)45-52
ISSN0166-218X
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Distance
  • Eccentricity
  • Periphery
  • Total domination number

Fingerprint

Dive into the research topics of 'A new lower bound for the total domination number in graphs proving a Graffiti.pc Conjecture'. Together they form a unique fingerprint.

Cite this