On 2-connected spanning subgraphs with low maximum degree (Q1127880)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On 2-connected spanning subgraphs with low maximum degree |
scientific article |
Statements
On 2-connected spanning subgraphs with low maximum degree (English)
0 references
10 August 1998
0 references
Given a graph \(G\), let a \(k\)-trestle of \(G\) be a 2-connected spanning subgraph of \(G\) of maximum degree at most \(k\). Also, let \(\chi(G)\) be the Euler characteristic of \(G\). This paper shows that every 3-connected graph \(G\) has a \((10-2\chi(G))\)-trestle. If \(\chi(G)<-4\), this is improved to \(8-2\chi(G)\), and for \(\chi(G)<-9\), this is further improved to \(6-2\chi(G)\). This result is shown to be best possible for almost all values of \(\chi(G)\) by the demonstration of 3-connected graphs embedded on each surface of Euler characteristic \(\chi<1\) which have no \((5-2\chi)\)-trestle. Also, it is shown that a 4-connected graph embeddable on a surface with non-negative Euler characteristic has a 3-trestle, approaching a conjecture of Nash-Williams.
0 references
graph theory
0 references
surfaces
0 references
spanning subgraphs
0 references
Hamiltonian cycles
0 references