A counterexample to conjecture of Barefoot, Harary, and Jones
A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if for each \(x\in V(G)-S\) there exists \(y\in S\) adjacent to \(x\). The domination number \(\alpha(G)\) of \(G\) is the minimum number of vertices of a dominating set in \(G\). Further the independent domination number \(\alpha'(G)\) of \(G\) is the minimum number of vertices of an independent (i.e. containing no two adjacent vertices) dominating set in \(G\). \textit{C. Barefoot}, \textit{F. Harary} and \textit{K. F. Jones} [Graphs Comb. 7, No. 2, 205-208 (1991; Zbl 0728.05033)] conjectured that for any 3-connected cubic graph \(G\) the difference \(\alpha'(G)-\alpha(G)\) is either 0 or 1. The authors of this paper present a sequence of 3- connected cubic graphs \(G_ k\) for positive integers \(k\) and assert that for any of them \(\alpha(G_ k)=6k\), \(\alpha'(G_ k)=6k+\lceil k/4\rceil\) and thus the difference \(\alpha'-\alpha\) may be arbitrarily large. Proof is omitted; the authors assert that it is tedious.
- Domination and irredundance in cubic graphs
- On the independent domination number of regular graphs
- On a Problem Concerning k-Subdomination Numbers of Graphs
- Domination versus independent domination in cubic graphs
- The independent domination number of a cubic 3-connected graph can be much larger than its domination number
- The domination and independent domination numbers of some families of snarks
This page was built for publication: A counterexample to conjecture of Barefoot, Harary, and Jones
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366962)
