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
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