On the maximum induced forests of a connected cubic graph without triangles (Q757394): 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 02:08, 5 March 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