Minimal graphs for hamiltonian extension

2019/12/10 by Picouleau, Christophe
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1912.04634

Abstract

For every n≥ 3 we determine the minimum number of edges of graph with n vertices such that for any non edge xy there exits a hamiltonian cycle containing xy.

Related

• Graphs with Many Hamiltonian Paths
• On the Minimum Number of Hamiltonian Cycles in Regular Graphs
• The minimum number of Hamilton cycles in a hamiltonian threshold graph of a prescribed order
• A Size Bound for Hamilton Cycles
• Hamiltonian graphs of given order and minimum algebraic connectivity