Non-revisiting paths on surfaces with low genus

DOI10.1016/S0012-365X(97)00151-9MaRDI QIDQ1379985zbMATH OpenFDO

Authors Hari Pulapaka, Andrew Vince

Publication date 25 February 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(97)00151-9

zbMATH Keywords

facegenusKlein bottlenon-revisiting pathorientable surfacespathpolytopeprojective planerevisiting pathtorus

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

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.

Recommendations

• Nonrevisiting paths on surfaces
• Nonrevisiting cycles on surfaces
• Maximal nonrevisiting paths in simple polytopes

Cites work

• \(W_ v\) paths in the projective plane
• A 3-Sphere Counterexample to the W_v-Path Conjecture
• Decomposition theorems for the torus, projective plane and Klein bottle
• Graph minors. VII: Disjoint paths on a surface
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 16301 (Why is no real title available?)
• scientific article; zbMATH DE number 3213126 (Why is no real title available?)
• Nonrevisiting paths on surfaces
• On a lemma of Fullerton and Braunschweiger
• On essential and inessential polygons in embedded graphs
• The d-Step Conjecture and Its Relatives
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• W\({}_ V\) paths on the torus
• Wv paths on 3-polytopes

Cited in

(5)

• Nonrevisiting cycles on surfaces
• On essential and inessential polygons in embedded graphs
• Nonrevisiting paths on surfaces
• Connectivity and \(W_v\)-paths in polyhedral maps on surfaces
• The Mani-Walkup Spherical Counterexamples to the W_v-Path Conjecture are Not Polytopal

This page was built for publication: Non-revisiting paths on surfaces with low genus

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