Necessary Conditions for Hamiltonicity & a New Idea

We are testing the properties based version of the program by generating conditions for a graph to be hamiltonian, a widely-studied graph property. We are on round 17; we have been finding counterexamples by hand as we test the program. The objects the program currently “knows” are listed below; the non-hamiltonian objects include the Petersen Graph and the Tutte Graph. So the conjectured conditions, taken together, should exclude these graphs.

The “theory” the program knows is that being 2-connected and having the van_den_heuvel property are necessary conditions for any hamiltonian graph. (The code for these and many of the properties we are using, together with the complete list of currently possible properties, as well as the graphs mentioned below, can be found here.)¬† So the program cannot make any conjectures which are implied by these facts.

In a previous round, when the Tutte Graph became a problem—the program was not finding any separating properties, Nico suggested using the invariant-relation program to conjecture a property that holds for hamiltonian graphs—using exaclty the example objects we were using for property-conjectures (then any conjectures, while possibly false for hamiltonian graphs in general, are guaranteed to be true for, at least, these graphs)—but which is false for the Tutte graph. One of these conjectures was that: if a graph is hamiltonian then its independence number is no more than the sum of its girth and diameter. It was true for all our Hamiltonian examples and false for the Tutte graph. We called this property “anti tutte” and added it to the program.

That’s the property that shows up in the following round of conjectures—and the reason it shows up.

hamiltonian_objects = [graphs.CompleteGraph(3), graphs.CompleteGraph(4), graphs.CompleteGraph(5), c6ee, c5chord, graphs.DodecahedralGraph(), c8chorded, c8chords, graphs.ClebschGraph(), graphs.CycleGraph(4), prismy, c24, c26, graphs.BuckyBall()]
non_hamiltonian_objects = [graphs.PetersenGraph(), graphs.PathGraph(2), graphs.TutteGraph()]
objects = hamiltonian_objects + non_hamiltonian_objects

[(is_hamiltonian)->(((is_anti_tutte)&(is_van_den_heuvel))|(is_planar_transitive)), (is_hamiltonian)->(((is_anti_tutte)->(is_forest))->(is_planar_transitive))]


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