Disproof of a conjecture in the domination theory (Q1343234): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q122983345, #quickstatements; #temporary_batch_1706826133308 |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Igor Edm. Zverovich / rank | |||
Property / author | |||
Property / author: Q1199498 / rank | |||
Property / author | |||
Property / author: Igor Edm. Zverovich / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Vadim E. Zverovich / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: What is the difference between the domination and independent domination numbers of a cubic graph? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5572939 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4873765 / rank | |||
Normal rank |
Revision as of 11:39, 23 May 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
0 references