The Largest Bond in 3-Connected Graphs
Melissa Flynn · 2017
A graph G is connected if given any two vertices, there is a path between them. A bond B is a minimal edge set in G such that G − B has more components than G. We say that a connected graph is dual Hamiltonian if its largest bond has size |E(G)|−|V (G)|+2. In this thesis we verify the conjecture that any simple 3-connected graph G has a largest bond with size at least Ω(nlog32) (Ding, Dziobiak, Wu, 2015 [3]) for a variety of graph classes including planar graphs, complete graphs, ladders, Mo bius ladders and circular ladders, complete bipartite graphs, some unique (3,g)- cages, the generalized Petersen graph, and some small hypercubes. We will also go further to prove that a variety of these graph classes not only satisfy the conjecture, but are also dual Hamiltonian.