Multiple factor NordhausGaddum type results for domination and total domination

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

A NordhausGaddum-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 examine the sum and product of γt( G1), γt( G2),..., γt( Gk) and the sum of γ( G1),γ( G2),...,γ( Gk) where G1G2⊕⋯⊕ Gk= Kn for positive integers n and k, γ(G) is the domination number and γt(G) is total domination number of a graph G. We show that ∑j=1kγ( Gj)≤(k-1)n+1 with equality if and only if Gi= Kn for some i∈1,...,k. For n≥7, 3≤k≤n-2 and δ( Gi)≥1 for each i∈1,2,...,k, we show that ∑j=1k γt( Gj)≤(k-1)(n+1).

Original languageEnglish
Pages (from-to)1137-1142
Number of pages6
JournalDiscrete Applied Mathematics
Volume160
Issue number7-8
DOIs
Publication statusPublished - May 2012

Keywords

  • Domination
  • NordhausGaddum
  • Total domination

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Multiple factor NordhausGaddum type results for domination and total domination'. Together they form a unique fingerprint.

Cite this