Connectivity and W_v-paths in polyhedral maps on surfaces

DOI10.1007/S00454-017-9868-9MaRDI QIDQ2408192zbMATH OpenOpenAlexFDO

Authors Michael D. Plummer, Dong Ye, Xiaoya Zha

Publication date 10 October 2017

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06402

zbMATH Keywords

\(W_v\)-path conjecturehomotopy classlocal connectivitypolyhedral embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Relations of low-dimensional topology with graph theory (57M15)

Abstract: The $W_v$-Path Conjecture due to Klee and Wolfe states that any two vertices of a simple polytope can be joined by a path that does not revisit any facet. This is equivalent to the well-known Hirsch Conjecture. Klee proved that the $W_v$-Path Conjecture is true for all 3-polytopes (3-connected plane graphs), and conjectured even more, namely that the $W_v$-Path Conjecture is true for all general cell complexes. This general $W_v$-Path Conjecture was verified for polyhedral maps on the projective plane and the torus by Barnette, and on the Klein bottle by Pulapaka and Vince. Let $G$ be a graph polyhedrally embedded in a surface $Sigma$, and $x,y$ be two vertices of $G$. In this paper, we show that if there are three internally disjoint $(x,y)$-paths which are homotopic to each other, then there exists a $W_v$-path joining $x$ and $y$. For every surface $Sigma$, define a function $f(Sigma)$ such that if for every graph polyhedrally embedded in $Sigma$ and for a pair of vertices $x$ and $y$ in $V(G)$, the local connectivity $kapp{a}_G(x,y)gef(Sigma)$, then there exists a $W_v$-path joining $x$ and $y$. We show that $f(Sigma)=3$ if $Sigma$ is the sphere, and for all other surfaces $3-au(Sigma)lef(Sigma)le9-4chi(Sigma)$, where $chi(Sigma)$ is the Euler characteristic of $Sigma$, and $au(Sigma)=chi(Sigma)$ if $chi(Sigma)<-1$ and 0 otherwise. Further, if $x$ and $y$ are not cofacial, we prove that $G$ has at least $kapp{a}_G(x,y)+4chi(Sigma)-8$ internally disjoint $W_v$-paths joining $x$ and $y$. This bound is sharp for the sphere. Our results indicate that the $W_v$-path problem is related to both the local connectivity $kapp{a}_G(x,y)$, and the number of different homotopy classes of internally disjoint $(x,y)$-paths as well as the number of internally disjoint $(x,y)$-paths in each homotopy class.

Review text

The paper deals with the \(W_v\)-path conjecture on closed surfaces and others. Starting by recalling the known facts about this conjecture and mentioning the equivalent conjectures in special cases, the paper continues with results giving several bounds for the values of a function \(f(\Sigma)\) defined to give a lower bound for the local connectivity of the embedded graph. Some of the formulae given for this function is related to the Euler characteristic of the underlying surface. Also, there are formulae on the number of components of the intersection of paths with a face of the graph, on the internally disjoint non-revisiting \((x,y)\)-paths, etc.

Recommendations

• W\({}_ V\) paths on the torus
• \(W_ v\) paths in the projective plane
• The Mani-Walkup Spherical Counterexamples to the W_v-Path Conjecture are Not Polytopal
• Non-revisiting paths on surfaces with low genus
• A local property of polyhedral maps on compact two-dimensional manifolds

Cites work

• W _v and W _e Paths on Simple 3-Polytopes
• \(W_ v\) paths in the projective plane
• A 2-manifold of genus 8 without the \(W_ v\)-property
• A 3-Sphere Counterexample to the W_v-Path Conjecture
• A counterexample to the Hirsch conjecture
• Graphs on surfaces
• Heawood's theorem and connectivity
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• Non-revisiting paths on surfaces with low genus
• Nonrevisiting paths on surfaces
• On essential and inessential polygons in embedded graphs
• On the face touching number
• Paths on Polyhedra. I
• Paths on Polytopes
• 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

(4)

• \(W_ v\) paths in the projective plane
• A 2-manifold of genus 8 without the \(W_ v\)-property
• The Mani-Walkup Spherical Counterexamples to the W_v-Path Conjecture are Not Polytopal
• W\({}_ V\) paths on the torus

This page was built for publication: Connectivity and \(W_v\)-paths in polyhedral maps on surfaces

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