Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421223 | Discrete Applied Mathematics | 2012 | 6 Pages |
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 examine the sum and product of γt(G1),γt(G2),…,γt(Gk)γt(G1),γt(G2),…,γt(Gk) and the sum of γ(G1),γ(G2),…,γ(Gk)γ(G1),γ(G2),…,γ(Gk) where G1⊕G2⊕⋯⊕Gk=KnG1⊕G2⊕⋯⊕Gk=Kn for positive integers nn and kk, γ(G)γ(G) is the domination number and γt(G)γt(G) is total domination number of a graph GG. We show that ∑j=1kγ(Gj)≤(k−1)n+1 with equality if and only if Gi=KnGi=Kn for some i∈{1,…,k}i∈{1,…,k}. For n≥7n≥7, 3≤k≤n−23≤k≤n−2 and δ(Gi)≥1δ(Gi)≥1 for each i∈{1,2,…,k}i∈{1,2,…,k}, we show that ∑j=1kγt(Gj)≤(k−1)(n+1).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michael A. Henning, Ernst J. Joubert, Justin Southey,