Induced forests in cubic graphs (Q791532)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Induced forests in cubic graphs |
scientific article |
Statements
Induced forests in cubic graphs (English)
0 references
1984
0 references
Let G be a graph with vertex set V(G). Denote \(f(G)=\max \quad \{| A| /| V(G)|;A\subset V(G),\) A induces a fores\(t\}\). The author derives bounds on f(G) and consequently calculates that lim \(\inf_{n\to \infty}\{f(G)\); G is a cubic graph with girth at least \(n\}\) equals to 3/4.
0 references
cubic graph
0 references
girth
0 references
forest
0 references
independence ratio
0 references