|
|||||
 |
|
|
|
|
|
|
|
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. |
PDF Access Denied
We have not been able to recognize your IP address
216.73.216.158
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.
You may also contact us at
contact@msp.org
or by using our
contact form.
Or, you may purchase this single article for USD 30.00:
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). |
