Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2106.13372 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913962716561408 |
|---|---|
| author | Carlson, Erik Fletcher, Willem Montee, MurphyKate Nguyen, Chi Renders, Jarne Zhang, Xingyi |
| author_facet | Carlson, Erik Fletcher, Willem Montee, MurphyKate Nguyen, Chi Renders, Jarne Zhang, Xingyi |
| contents | A graph is \emph{hamiltonian-connected} if every pair of vertices can be connected by a hamiltonian path, and it is \emph{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 $\geq 3n/2$ edges. We construct an infinite family of graphs realizing this minimum. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_13372 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Graphs with Many Hamiltonian Paths Carlson, Erik Fletcher, Willem Montee, MurphyKate Nguyen, Chi Renders, Jarne Zhang, Xingyi Combinatorics 05C45, 90C35 A graph is \emph{hamiltonian-connected} if every pair of vertices can be connected by a hamiltonian path, and it is \emph{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 $\geq 3n/2$ edges. We construct an infinite family of graphs realizing this minimum. |
| title | Graphs with Many Hamiltonian Paths |
| topic | Combinatorics 05C45, 90C35 |
| url | https://arxiv.org/abs/2106.13372 |