Graphs with Large Disjunctive Total Domination Number
Michael Anthony Henning, Viroshan Naicker
Abstract
Let G be a graph with no isolated vertex. In this paper,
we study a parameter that is a relaxation of arguably the most
important domination parameter, namely the total domination number,
γt(G). A set S of vertices
in G is a disjunctive total dominating set of
G if every vertex is adjacent to a vertex of
S or has at least two vertices in S at
distance 2 from it. The disjunctive total domination
number, γdt(G), is the
minimum cardinality of such a set. We observe that
γdt(G)
≤γt(G). Let G be a connected
graph on n vertices with minimum degree
δ. It is known [J. Graph Theory 35 (2000),
21 13;45] that if δ≥2 and n
≥11, then γt(G) ≤4n/7.
Further [J. Graph Theory 46 (2004), 207 13;210] if
δ≥3, then γt(G)
≤n/2. We prove that if δ≥2 and n
≥8, then γdt(G)
≤n/2 and we characterize the extremal graphs.
Full Text: PDF PostScript