On independent domination number of regular graphs (Q1301709): Difference between revisions
From MaRDI portal
Latest revision as of 11:29, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On independent domination number of regular graphs |
scientific article |
Statements
On independent domination number of regular graphs (English)
0 references
10 April 2000
0 references
A subset \(S\) of the vertex set of a graph \(G\) is called independent, if no two of its vertices are adjacent in \(G\). An independent set in \(G\) is maximal, if it is not a proper subset of another independent set of \(G\). The minimum number of vertices of a maximal independent set is the independent domination number \(i(G)\) of \(G\). A conjecture of J. Haviland says that a regular graph \(G\) of degree \(\delta\leq n/2\) (where \(n\) is the number of vertices of \(G\)) has \(i(G)\leq\lceil 2n/3\rceil \delta/2\). In the paper this conjecture is disproved by giving two counterexamples. Then for a connected cubic graph \(G\) with \(n>3\) vertices the inequality \(i(G)\leq 2n/5\) is proved.
0 references
independent set
0 references
independent domination number
0 references
regular graph
0 references