2021/06/25 by Erik Carlson, Carlson, Erik, Willem Fletcher +7
Computer Science · Engineering · #05C45 #90C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2106.13372
openalex publication_date 2021/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is hamiltonian-connected if every pair of vertices can be connected by a hamiltonian path, and it is hamiltonian if it contains a hamiltonian cycle. We construct families of non-hamiltonian graphs for which the ratio of pairs of vertices connected by hamiltonian paths to all pairs of vertices approaches 1. We then consider minimal graphs that are hamiltonian-connected. It is known that any order-n graph that is hamiltonian-connected must have ≥ 3n/2 edges. We construct an infinite family of graphs realizing this minimum.