2018/06/17 by Oliver Knill, Knill, Oliver · 1 citation
Computer Science · Mathematics · #05C45 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology #Homotopy and Cohomology in Algebraic Topology #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1806.06436
openalex publication_date 2018/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Extending a theorem of Whitney of 1931 we prove that all connected d-graphs are Hamiltonian for positive d. A d-graph is a type of combinatorial manifold which is inductively defined as a finite simple graph for which every unit sphere is a (d-1)-sphere. A d-sphere is d-graph such that removing one vertex renders the graph contractible. A graph is contractible if there exists a vertex for which the unit sphere and the graph without that vertex are both contractible. These inductive definitions are primed with the assumptions that the empty graph 0 is the (-1)-sphere and that the one-point graph 1 is the smallest contractible graph. The proof is constructive and shows that unlike for general graphs, the complexity of the construction of Hamiltonian cycles in d-graphs is polynomial in the number of vertices of the graph.