Premium
Graphs with large total domination number
Author(s) -
Henning Michael A.
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200009)35:1<21::aid-jgt3>3.0.co;2-f
Subject(s) - combinatorics , mathematics , dominating set , domination analysis , vertex (graph theory) , connectivity , graph , discrete mathematics , degree (music) , bound graph , graph power , line graph , physics , acoustics
Let G = ( V , E ) be a graph. A set S ⊆ V is 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 ) ≤ 2 n /3. We show that if G is a connected graph of order n with minimum degree at least 2, then either γ t ( G ) ≤ 4 n /7 or G ∈ { C 3 , C 5 , C 6 , C 10 }. A characterization of those graphs of order n which are edge‐minimal with respect to satisfying G connected, δ( G ) ≥ 2 and γ t ( G ) ≥ 4 n /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. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 21–45, 2000