Spanning planar subgraphs of graphs in the torus and Klein bottle
type: Item
instance of: scholarly article
title: Spanning planar subgraphs of graphs in the torus and Klein bottle
zbMATH Open document ID: 0837.05049
author: Richard Brunet
author: Alice Metzlar
author: R. B. Richter
author: M. N. Ellingham
author: Zhicheng Gao
published in: Journal of Combinatorial Theory. Series B
publication date: 1996-05-13T00:00:00Z
review text: Since Whitney's 1931 major results on the Hamiltonian properties of planar graphs, many generalizations to graphs on surfaces have been found. Two concepts of interest in this respect are that of a \(k\)-walk and an \(m\)-tree. A \(k\)-walk in a graph is a closed walk that visits every vertex at least once and at most \(k\) times. An \(m\)-tree is a spanning tree with maximum degree at most \(m\). The paper under review contains a useful summary of known results about these properties for graphs embedded in surfaces. The torus and Klein bottle are the only surfaces for which the existence of 2-walks for 3-connected graphs is an open question. The main result of the paper settles this question by showing that every 3-connected graph embeddable in the torus or Klein bottle has a 2-walk and a 3-tree.
reviewed by: M.Marx
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 798755
zbMATH Keywords: embedding
zbMATH Keywords: \(k\)-walk
zbMATH Keywords: \(m\)-tree
zbMATH Keywords: planar graphs
zbMATH Keywords: surfaces
zbMATH Keywords: closed walk
zbMATH Keywords: spanning tree
zbMATH Keywords: torus
zbMATH Keywords: Klein bottle
MaRDI profile type: Publication
full work available at URL: jctb.1995.1041
OpenAlex ID: W2150450903
DOI: 10.1006/JCTB.1995.1041
Recommended article: Q4871147
Recommended article: The \(k\)-subconnectedness of planar graphs
Recommended article: On the two-connected planar spanning subgraph polytope
Recommended article: Subhamiltonian toroidal graphs
Recommended article: The 2-extendability of graphs on the projective plane, the torus and the Klein bottle
Recommended article: Spanning subsets of toroidal and Klein bottle embeddings
Recommended article: On the nonembeddability and crossing numbers of some toroidal graphs on the Klein bottle
Recommended article: On the restricted matching extension of graphs on the torus and the Klein bottle
Recommended article: Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface
Recommended article: Regular Connected Bipancyclic Spanning Subgraphs of Torus Networks
description: scientific article; zbMATH DE number 798755