On 2-connected spanning subgraphs with low maximum degree
type: Item
instance of: scholarly article
title: On 2-connected spanning subgraphs with low maximum degree
zbMATH Open document ID: 0904.05027
author: Daniel P. Sanders
author: Yue Zhao
published in: Journal of Combinatorial Theory. Series B
publication date: 1998-08-10T00:00:00Z
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.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1186396
zbMATH Keywords: graph theory
zbMATH Keywords: surfaces
zbMATH Keywords: spanning subgraphs
zbMATH Keywords: Hamiltonian cycles
MaRDI profile type: Publication
OpenAlex ID: W2015334554
cites work: 2-connected spanning subgraphs of planar 3-connected graphs
cites work: Spanning planar subgraphs of graphs in the torus and Klein bottle
cites work: On the genus and connectivity of Hamiltonian graphs
cites work: Q4390602
cites work: 2‐connected coverings of bounded degree in 3‐connected graphs
cites work: Q4014627
cites work: Contractible triples in 3-connected graphs
cites work: Q5678882
cites work: Das Geschlecht des vollständigen paaren Graphen
cites work: Der vollständige paare Graph auf nichtorientierbaren Flächen.
cites work: On Hamilton cycles in certain planar graphs
cites work: Q3129827
cites work: On spanning trees and walks of low maximum degree
cites work: 4-connected projective planar graphs are Hamiltonian
cites work: Trees in triangulations
cites work: A Theorem on Planar Graphs
DOI: 10.1006/JCTB.1998.1836
description: scientific article; zbMATH DE number 1186396