On the maximum induced forests of a connected cubic graph without triangles (Q757394): Difference between revisions
From MaRDI portal
Removed claims |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Mao Lin Zheng / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Xiao-Yun Lu / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lower Bounds For Induced Forests in Cubic Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4063170 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On feedback vertex sets and nonseparating independent sets in cubic graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Induced forests in cubic graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three / rank | |||
Normal rank |
Latest revision as of 15:12, 21 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the maximum induced forests of a connected cubic graph without triangles |
scientific article |
Statements
On the maximum induced forests of a connected cubic graph without triangles (English)
0 references
1990
0 references
Let t(G) denote the cardinality of a maximum induced forest of a graph G with n vertices. This paper proves that t(G)\(\geq \frac{2n}{3}\) for any cubic graph G without triangles, except for two cubic graphs with \(n=8\) and \(t(G)=5\). This lower bound is best possible and implies that Speckenmeyer's conjecture is true with two exceptions.
0 references
induced forest
0 references
cubic graph
0 references