On a Nordhaus-Gaddum type problem for independent domination (Q1842161): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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 | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(94)00202-t / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2018411871 / rank | |||
Normal rank |
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