Nordhaus-Gaddum Type Results for Total Domination
Michael Anthony Henning, Ernst Joubert, Justin Southey
Abstract
A Nordhaus-Gaddum-type result is a (tight) lower or upper bound on the
sum or product of a parameter of a graph and its complement. In this
paper we study Nordhaus-Gaddum-type results for total domination. We
examine the sum and product of
γt(G1) and
γt(G2) where
G1 ⊕G2 = K(s,s), and
γt is the total domination number. We
show that the maximum value of the sum of the total domination numbers
of G1 and G2 is
2s+4, with equality if and only if G1 =
sK2 or G2 = sK2,
while the maximum value of the product of the total domination numbers
of G1 and G2 is
max{8s,⌊(s+6)2/4
⌋}.
Full Text: PDF PostScript