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
    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
    0 references
    cubic graph
    0 references
    girth
    0 references
    forest
    0 references
    independence ratio
    0 references