Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949541 | Discrete Applied Mathematics | 2017 | 8 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 Henning et al. (2011) the authors (Henning et al.) show that if G1âG2=K(s,s), and neither G1 nor G2 has isolated vertices, then the product γt(G1)γt(G2) is at most max{8s,â(s+6)2â4â}, where γt is the total domination number. In this paper we will use a vertex disjoint star covering technique, to significantly improve the mentioned bound. In particular, we will show that if G1âG2=K(s,s), and neither G1 nor G2 has isolated vertices, then γt(G1)γt(G2)â¤max{8s,â(s+5)2â4â}.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ernst J. Joubert,