On 2-connected spanning subgraphs with low maximum degree

DOI10.1006/JCTB.1998.1836MaRDI QIDQ1127880zbMATH OpenOpenAlexFDO

Authors Daniel P. Sanders, Yue Zhao

Publication date 10 August 1998

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d3a0b1ba7f812b24f4070311e8e15f68ca1bda91

zbMATH Keywords

graph theoryHamiltonian cyclesspanning subgraphssurfaces

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

Review text

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.

Recommendations

• 2-connected spanning subgraphs with low maximum degree in locally planar graphs
• On k-trestles in polyhedreal graphs
• Spanning Trees with Bounded Maximum Degrees of Graphs on Surfaces
• 2‐connected coverings of bounded degree in 3‐connected graphs

Cites work

• 2-connected spanning subgraphs of planar 3-connected graphs
• 2‐connected coverings of bounded degree in 3‐connected graphs
• 4-connected projective planar graphs are Hamiltonian
• A Theorem on Planar Graphs
• Contractible triples in 3-connected graphs
• Das Geschlecht des vollständigen paaren Graphen
• Der vollständige paare Graph auf nichtorientierbaren Flächen.
• scientific article; zbMATH DE number 1002024 (Why is no real title available?)
• scientific article; zbMATH DE number 68918 (Why is no real title available?)
• scientific article; zbMATH DE number 1156578 (Why is no real title available?)
• scientific article; zbMATH DE number 3414331 (Why is no real title available?)
• On Hamilton cycles in certain planar graphs
• On spanning trees and walks of low maximum degree
• On the genus and connectivity of Hamiltonian graphs
• Spanning planar subgraphs of graphs in the torus and Klein bottle
• Trees in triangulations

Cited in

(14)

• Subgraphs of graphs on surfaces with high representativity
• On minimally 3-connected graphs on a surface
• Surfaces, tree-width, clique-minors, and partitions
• Long cycles in graphs on a fixed surface
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
• On spanning trees and walks of low maximum degree
• Generating Low-Degree 2-Spanners
• A Dirac theorem for trestles
• On k-trestles in polyhedreal graphs
• On 2-connected spanning subgraphs with bounded degree in \(K _{1,r }\)-free graphs
• Two local and one global properties of 3-connected graphs on compact 2-dimensional manifolds
• 2-connected spanning subgraphs with low maximum degree in locally planar graphs
• Finding large cycles in Hamiltonian graphs

This page was built for publication: On 2-connected spanning subgraphs with low maximum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127880)