The Largest Bond in 3-Connected Graphs

Flynn, Melissa (2017) The Largest Bond in 3-Connected Graphs. Undergraduate thesis, under the direction of Haidong Wu from Mathematics, The University of Mississippi.


Download (1MB) | Preview


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.

Item Type: Thesis (Undergraduate)
Creators: Flynn, Melissa
Student's Degree Program(s): B.S. in Mathematics
Thesis Advisor: Haidong Wu
Thesis Advisor's Department: Mathematics
Institution: The University of Mississippi
Subjects: Q Science > QA Mathematics
Depositing User: Melissa Flynn
Date Deposited: 12 May 2017 15:18
Last Modified: 12 May 2017 15:18

Actions (login required)

View Item View Item