Induced forests in cubic graphs (Q791532): 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 01:14, 5 March 2024
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
