Henning, Michael, and Joubert, Ernst and Southey, Justin - Nordhaus-Gaddum Type Results for Total Domination

dmtcs:530 - Discrete Mathematics & Theoretical Computer Science, December 30, 2011, Vol. 13 no. 3
Nordhaus-Gaddum Type Results for Total Domination

Authors: Henning, Michael, and Joubert, Ernst and Southey, Justin

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 ⌋}.


Source : oai:HAL:hal-00993071v1
Volume: Vol. 13 no. 3
Section: Graph Theory
Published on: December 30, 2011
Submitted on: March 30, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 62 times.
This article's PDF has been downloaded 136 times.