Graph Theory and the Barnette Conjecture
John Key and Therese Relucio
David W. Barnette conjectured that the vertices of certain planar graphs can be traversed in a cycle along their edges. 50 years later and the conjecture is still unproven. Continuing off of last summer’s students’ research, we coded the conjecture as a SAT solution so that a solver could find a cycle on 1000 vertices in under 10 seconds. We then considered the graph of all disjoint cycle coverings of Barnette’s planar graphs and studied its structure. We finished the summer by writing algorithms that were designed to find such a cycle in the graph, which if proven to work without error, would prove the conjecture. Further research includes refining the algorithms and proving their steps.
Friday, September 18 at 3:30pm to 4:30pmVirtual Event
If you are a member of the University of Dallas community, please log in with your MyUD username and password (Windows and Wifi login credentials).
If you are not a member of the University of Dallas community, please login via one of the options below to access our interactive calendar.Login with Facebook Login with Google Login with Twitter Login with LinkedIn
The UD calendar is for university events only. All event submissions are reviewed and approved before posting. Please allow up to two days for events to appear.