Non-revisiting paths on surfaces with low genus
type: Item
instance of: scholarly article
title: Non-revisiting paths on surfaces with low genus
zbMATH Open document ID: 0889.05041
DOI: 10.1016/S0012-365X(97)00151-9
published in: Discrete Mathematics
publication date: 1998-02-25T00:00:00Z
review text: A revisiting path to a face of a graph of a polytope, is a path that leaves the face at a vertex \(x\), and revisits at a vertex \(y\) (with no intersection with the face in between). The non-revisiting path conjecture says that any two vertices of a polytope \(P\) can be joined by a path that does not revisit any face of \(P\). The authors have previously proved this false for all orientable surfaces of genus \(g\geq 2\) and all nonorientable surfaces of nonorientable genus \(h\geq 4\). Here it is shown by an elementary proof that the conjecture is true for the sphere, projective plane, torus and Klein bottle, only leaving the case of the connected sum of three copies of the projective plane still open.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1121502
zbMATH Keywords: revisiting path
zbMATH Keywords: polytope
zbMATH Keywords: path
zbMATH Keywords: face
zbMATH Keywords: non-revisiting path
zbMATH Keywords: orientable surfaces
zbMATH Keywords: genus
zbMATH Keywords: projective plane
zbMATH Keywords: torus
zbMATH Keywords: Klein bottle
author: Hari Pulapaka
author: Andrew Vince
reviewed by: Chris Jagger
MaRDI profile type: Publication
cites work: Wv paths on 3-polytopes
cites work: \(W_ v\) paths in the projective plane
cites work: Decomposition theorems for the torus, projective plane and Klein bottle
cites work: W\({}_ V\) paths on the torus
cites work: Q3844775
cites work: Q5340330
cites work: On a lemma of Fullerton and Braunschweiger
cites work: The d-Step Conjecture and Its Relatives
cites work: The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
cites work: A 3-Sphere Counterexample to the Wv-Path Conjecture
cites work: Nonrevisiting paths on surfaces
cites work: On essential and inessential polygons in embedded graphs
cites work: Graph minors. VII: Disjoint paths on a surface
cites work: Q3972954
description: scientific article; zbMATH DE number 1121502