|
|||||
 |
|
|
|
|
|
|
|
Graphs with
many hamiltonian paths
Erik Carlson, Willem Fletcher, MurphyKate Montee, Chi Nguyen, Jarne Renders and Xingyi Zhang |
|
Vol. 18 (2025), No. 4, 613–627
|
Abstract |
|
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 nonhamiltonian 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- graph that is hamiltonian-connected must have edges. We construct an infinite family of graphs realizing this minimum. |
Keywords
hamiltonian, hamiltonian-connected, pair-strung
|
Mathematical Subject Classification
Primary: 05C45, 05C38
|
Milestones
Received: 4 May 2023
Revised: 26 March 2024
Accepted: 1 April 2024
Published: 30 July 2025
Communicated by Ann N. Trenk
|
Authors |
| Erik Carlson | |
| Seattle, WA United States |
|
| Willem Fletcher | |
| Department of Computer Science Brown University Providence, RI United States |
|
| MurphyKate Montee | |
| Department of Mathematics and
Statistics Carleton College Northfield, MN United States |
|
| Chi Nguyen | |
| Department of Mathematics Virginia Polytechnic Institute and State University Blacksburg, VA United States |
|
| Jarne Renders | |
| Department of Computer Science KU Leuven Campus Kulak-Kortrijk Kortrijk Belgium |
|
| Xingyi Zhang | |
| Department of Mathematics and
Statistics Carleton College Northfield, MN United States |
|
| © 2025 MSP (Mathematical Sciences Publishers). |
