Honors Theses
Date of Award
2017
Document Type
Undergraduate Thesis
Department
Mathematics
First Advisor
Haidong Wu
Relational Format
Dissertation/Thesis
Abstract
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.
Recommended Citation
Flynn, Melissa, "The Largest Bond in 3-Connected Graphs" (2017). Honors Theses. 695.
https://egrove.olemiss.edu/hon_thesis/695
Accessibility Status
Searchable text