On a Nordhaus-Gaddum type problem for independent domination (Q1842161): Difference between revisions

The independent domination number \(i(G)\) of a graph \(G\) is the minimum number of vertices of a subset of the vertex set of \(G\) which is simultaneously independent (consisting of pairwise non-adjacent vertices) and dominating (each vertex either is in it, or is adjacent to a vertex in it). A function \(f\) is studied; \(f(p)\) is the minimum value of the product \(i(G)i (\overline G)\) over all graphs \(G\) with \(p\) vertices (the symbol \(\overline G\) denotes the complement of \(G)\). It is proved that \[ \lim_{p \to \infty} {f(p) \over p^ 2} = {1 \over 16}. \]