On independent domination number of regular graphs (Q1301709): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q221699 |
Changed an Item |
||
Property / author | |||
Property / author: Peter Che Bor Lam / rank | |||
Normal rank |
Revision as of 08:01, 11 February 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