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

dmtcs:530 - Discrete Mathematics & Theoretical Computer Science, December 30, 2011, Vol. 13 no. 3 - https://doi.org/10.46298/dmtcs.530
Nordhaus-Gaddum Type Results for Total DominationArticle

Authors: Michael Henning 1; Ernst Joubert 1; Justin Southey 1

  • 1 Department of Mathematics [University of Johannesburg]

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


Volume: Vol. 13 no. 3
Section: Graph Theory
Published on: December 30, 2011
Accepted on: June 9, 2015
Submitted on: March 30, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 370 times.
This article's PDF has been downloaded 652 times.