The product of the independent domination numbers of a graph and its complement (Q1179268)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The product of the independent domination numbers of a graph and its complement |
scientific article |
Statements
The product of the independent domination numbers of a graph and its complement (English)
0 references
26 June 1992
0 references
In an undirected, simple graph \(G\), let \(i(G)\) denote the smallest cardinality of a maximal independent set of vertices. The quantity \(i(G)\) is also known as the independent domination number of \(G\). The authors improve the best known upper bound for \(i(G)i(\bar G)\) from \(\lceil p(p+2)/4\rceil\) to \(\min\{(p+3)^ 2/8,(p+8)^ 2/10.8\}\), where \(p\) is the order of \(G\) and \(\bar G\) is the complement of \(G\).
0 references
independent domination number
0 references
0 references