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.

gould

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:

[((has_radius_equal_diameter)&(is_eulerian))->(is_hamiltonian)]

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

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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