2009/09/30 by Paul Prue, Travis Scrimshaw · 19 citations
Computer Science · Mathematics · #Combinatorics #Configuration space #Discrete mathematics #Distance #Geometric and Algebraic Topology #Graph #Graph power #Homotopy and Cohomology in Algebraic Topology #Line graph #Mathematical analysis #Mathematics #Path graph #Shortest path problem #Subspace topology #Topological and Geometric Data Analysis #Vertex (graph theory) #math.GT #msc:20F36 #msc:20F65 #msc:55R80
paper · pdf · doi:10.1016/j.topol.2014.09.009
published in Topology and its Applications 178, 136-145 (Elsevier BV) · 8 pages, 3 figures
arxiv created 2014/07/06 · openalex publication_date 2014/09/25 · arxiv updated 2019/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
In his PhD thesis, Abrams proved that, for a natural number n and a graph G with at least n vertices, the n-strand configuration space of G deformation retracts to a compact subspace, the discretized n-strand configuration space, provided G satisfies two conditions: each path between distinct essential vertices (vertices of degree not equal to 2) is of length at least n+1 edges, and each path from a vertex to itself which is not nullhomotopic is of length at least n+1 edges. Using Forman's discrete Morse theory for CW-complexes, we show the first condition can be relaxed to require only that each path between distinct essential vertices is of length at least n-1.