On the Prevalence of Bridge Graphs Among Non-3-Connected Cubic Non-Hamiltonian Graphs

2019/08/28 by Advani, Rishi
#05C45 (Primary) 05C40 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1908.10528

Abstract

There is empirical evidence supporting the claim that almost all cubic non-Hamiltonian graphs are bridge graphs. In this paper, we pose a related conjecture and prove that the original claim holds for non-3-connected graphs if the conjecture is true.

Related

• Hamiltonian cubic bipartite graphs
• Hamilton cycles in infinite cubic graphs
• A sufficient condition for cubic 3-connected plane bipartite graphs to be hamiltonian
• Algorithmic proof of Barnette's Conjecture
• Hamiltonian cycles in planar cubic graphs with facial 2-factors, and a new partial solution of Barnette's Conjecture