Round #12 Hamiltonicity sufficient conditions

We have been testing the properties-conjectures program by running necessary and sufficient conditions for the hamiltonicity of a graph and finding and adding counterexamples by hand. All the kinks seem to be worked out now. Nico has been visiting VCU for the last 3 weeks and is leaving on Monday—I’ve learned a lot while he’s been here. He also gave 2 talks in our Discrete Math Seminar.


Ron Gould gave us a counterexample (pictured) to the last lower bound conjecture: this graph is 2-connected, regular and eulerian – but not hamiltonian. We added this graph to the graphs the program “knows” and got the following new conjecture:


This should be interpreted: If a graph has equal radius and diameter and is eulerian then the graph is hamiltonian.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s