Skip to Main content Skip to Navigation
Journal articles

Nordhaus-Gaddum Type Results for Total Domination

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 ⌋}.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00993071
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Monday, May 19, 2014 - 3:44:45 PM
Last modification on : Friday, April 20, 2018 - 12:00:03 PM
Long-term archiving on: : Monday, April 10, 2017 - 11:47:31 PM

File

1830-6703-1-PB.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00993071, version 1

Collections

Citation

Michael Henning, Ernst Joubert, Justin Southey. Nordhaus-Gaddum Type Results for Total Domination. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.87-96. ⟨hal-00993071⟩

Share

Metrics

Record views

302

Files downloads

1386