Some nordhaus‐‐ gaddum‐type results
Wayne Goddard, Michael A. Henning, Henda C. Swart · Journal of Graph Theory · 1992
Abstract A Nordhaus‐‐Gaddum‐type result is a (tgiht) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper some variations are considered. First, the sums and products of ψ(G1) and ψ(G2) are examined where G1 ⊕ G2 = K(s, s), and ψ is the independence, domination, or independent domination number, inter alia. In particular, it is shown that the maximum value of the product of the domination numbers of G1 and G2 is [(s/2 + 2)2] for s ≥ 3. Thereafter it is shown that for H1 ⊕ H2 ⊕ H3 = Kp, the maximum product of the domination numbers of H2, H2, and H3 is p3/27 + Θ(p2).