Graphs with large total domination number

Research output: Contribution to journalArticlepeer-review

96 Citations (Scopus)

Abstract

Let G= (V,E) be a graph. A set S⊆ Vis a total dominating set if every vertex of V is adjacent to some vertex in S. The total domination number of G, denoted by γt(G), is the minimum cardinality of a total dominating set of G. We establish a property of minimum total dominating sets in graphs. If G is a connected graph of order n≥3, then (see [3]) γt,(G)≤2n/3. We show that if G is a connected graph of order n with minimum degree at least 2, then either γt(G) ≤ 4n/7 or Gε {C3, C5, C6, C10}. A characterization of those graphs of order n which are edge-minimal with respect to satisfying G connected, δ(G) ≥ 2 and γt(G) ≥ 4n/7 is obtained. We establish that if G is a connected graph of size q with minimum degree at least 2, then γt(G) ≤ (q+2)/2. Connected graphs G of size q with minimum degree at least 2 satisfying γt(G) ≥ q/2 are characterized.

Original languageEnglish
Pages (from-to)21-45
Number of pages25
JournalJournal of Graph Theory
Volume35
Issue number1
DOIs
Publication statusPublished - 2000
Externally publishedYes

Keywords

  • Bounds
  • Minimum degree two
  • Total domination

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Graphs with large total domination number'. Together they form a unique fingerprint.

Cite this