Total domination in graphs with diameter 2

Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning, Anders Yeo

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. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, γt(G)≤1+nln(n). This bound is optimal in the sense that given any ε>0, there exist graphs G with diameter 2 of all sufficiently large even orders n such that γt(G)>(14+ε)nln(n).

Original languageEnglish
JournalJournal of Graph Theory
Volume75
Issue number1
Pages (from-to)91-103
ISSN0364-9024
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • diameter-2
  • hypergraphs
  • total domination
  • transversals

Fingerprint

Dive into the research topics of 'Total domination in graphs with diameter 2'. Together they form a unique fingerprint.

Cite this