On a Nordhaus-Gaddum type problem for independent domination (Q1842161): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: The product of the independent domination numbers of a graph and its complement / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the product of upper irredundance numbers of a graph and its complement / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Complementary Graphs / rank | |||
Normal rank |
Revision as of 13:06, 23 May 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