Subdivisions of a graph of maximal degree \(n+1\) in graphs of average degree \(n+\epsilon\) and large girth (Q5955200)

From MaRDI portal
scientific article; zbMATH DE number 1703949
Language Label Description Also known as
English
Subdivisions of a graph of maximal degree \(n+1\) in graphs of average degree \(n+\epsilon\) and large girth
scientific article; zbMATH DE number 1703949

    Statements

    Subdivisions of a graph of maximal degree \(n+1\) in graphs of average degree \(n+\epsilon\) and large girth (English)
    0 references
    0 references
    13 February 2002
    0 references
    In the paper it is proved that for every integer \(n\geq 2\) and every \(\epsilon>0\), there is a least positive integer \(t(n,\epsilon)\) such that for every finite graph of average degree at least \(n+\epsilon\) and of girth at least \(t(n,\epsilon)\) contains a subdivision of the complete graph on \(n+2\) vertices. The values of \(t(2,\epsilon)\) are determined for every \(\epsilon>0\).
    0 references
    average degree
    0 references
    girth
    0 references
    series-parallel graph
    0 references
    subdivision
    0 references
    subgraph
    0 references

    Identifiers