On a Nordhaus-Gaddum type problem for independent domination (Q1842161): Difference between revisions
From MaRDI portal
Latest revision as of 10:58, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a Nordhaus-Gaddum type problem for independent domination |
scientific article |
Statements
On a Nordhaus-Gaddum type problem for independent domination (English)
0 references
17 April 1995
0 references
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}. \]
0 references
Nordhaus-Gaddum type problem
0 references
independent domination number
0 references