The maximum diameter of total domination edge-critical graphs

Michael A. Henning, Lucas C. Van Der Merwe

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γt(G) of G. The graph G is total domination edge-critical if for every edge e in the complement of G, γt(G+e)<γt(G). We call such graphs γtEC. If G isγtEC and γt(G)=k, we say that G is ktEC. For k<2, we show that the maximum diameter of a ktEC graph is at least ⌊3(k-1)/2⌋ and this bound is sharp for small k≤6.

Original languageEnglish
Pages (from-to)397-404
Number of pages8
JournalDiscrete Mathematics
Issue number2
Publication statusPublished - 28 Jan 2012


  • Bounds
  • Diameter
  • Edge-critical
  • Total domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'The maximum diameter of total domination edge-critical graphs'. Together they form a unique fingerprint.

Cite this