Graphs with Many Hamiltonian Paths

MaRDI QIDQ6505133arXivFDO

Authors Erik Carlson, Willem Fletcher, Murphykate Montee, Chi Mai Nguyen, Xingyi Zhang

Published in arXiv

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Programming involving graphs or networks (90C35)

Abstract: 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. Every hamiltonian-connected graph is hamiltonian, however we also construct families of nonhamiltonian graphs with `many' hamiltonian paths, where 'many' is interpreted with respect to the number of pairs of vertices connected by hamiltonian paths. We then consider minimal graphs that are hamiltonian-connected; we show that any order-$n$ graph that is hamiltonian-connected graphs must have $geq3n/2$ edges, and we construct an infinite family of graphs realizing this minimum.

This page was built for publication: Graphs with Many Hamiltonian Paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505133)