Disproof of a conjecture in the domination theory (Q1343234): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:01, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Disproof of a conjecture in the domination theory |
scientific article |
Statements
Disproof of a conjecture in the domination theory (English)
0 references
1 February 1995
0 references
A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating, if for each vertex \(x\in V(G)- S\) there exists a vertex \(y\in S\) adjacent to \(x\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\alpha(G)\) of \(G\). The minimum number of vertices of a set which is simultaneously dominating and independent in \(G\) is the independent domination number \(\alpha'(G)\) of \(G\). The authors disprove a conjecture by \textit{C. Barefoot}, \textit{F. Harary} and \textit{K. F. Jones} [Graphs Comb. 7, No. 2, 205-208 (1991; Zbl 0728.05033)] that the difference \(\alpha'(G)- \alpha(G)\) for cubic graphs with connectivity three does not exceed 1. They prove that for any \(c\in \{0,1,2,3\}\) and any integer \(k\geq 0\) there exist infinitely many cubic graphs \(G\) with connectivity \(c\) for which \(\alpha'(G)- \alpha(G)= k\). They express a conjecture that an analogous assertion holds also for regular graphs of degree greater than three.
0 references
dominating set
0 references
domination number
0 references
independent domination number
0 references
cubic graphs
0 references
connectivity
0 references
regular graphs
0 references