Necessary Conditions for Hamiltonicity

We have added new features to the program including the ability to conjecture necessary or sufficient conditions for any property, together with the ability to add known theory.

In this example we wanted necessary conditions for a graph to be Hamiltonian. We read Ron Gould‘s three surveys of results on Hamiltonicity and related topics, and found many more sufficient conditions than necessary conditions. Ron explains this is because almost every graph is Hamiltonian. The two known necessary conditions we told the program were that Hamiltonian graphs are necessarily 2-connected, and that they satisfy a Laplacian eigenvalue condition due to van den Heuvel.

proptheory = [is_two_connected, is_van_den_heuvel]

The way that the Dalmatian heuristic and the “theory” component work is that each necessary condition defines a property that does not hold for at least one object for which all the given “theory” conditions do hold. In other words, if the program conjectures a necessary condition C, then the class of graphs which are 2-connected, van den Heuvel and have property C must be strictly smaller than the class of graphs which are just 2-connected and van den Heuvel. In this sense the conjecture is informative.

Furthermore each subsequent conjecture must also exclude an object that had property C. So the addition of each conjecture leads to a tighter upper bound on a graph being Hamiltonian – in the best case the intersection of the conjectured properties exactly corresponds to the set of Hamiltonian graphs known to the program. Here are the conjectures:

  1. (is_hamiltonian)->((has_cycle_space_dimension_leq_card_positive_eigenvalues)->(is_planar))
  2. (is_hamiltonian)->((is_chordal)->(is_dirac))
  3. (is_hamiltonian)->(has_radius_leq_card_center)
  4. (is_hamiltonian)->((is_chordal)->(has_laplacian_energy_leq_average_vertex_temperature))
  5. (is_hamiltonian)->((has_perfect_matching)->(is_class1))
  6. (is_hamiltonian)->((is_traceable)&(is_van_den_heuvel))

The first thing to point out is that Conjecture 6 is true. While the program cannot conjecture that Hamiltonian graphs have the van den Heuvel property (this wouldn’t be informative), being traceable and van den Heuvel must be stronger than being van den Heuvel alone: that is, the program must have known some graph which is traceable and van den Heuvel but is not Hamiltonian. In fact several graphs have this property including the Tutte graph, the Meredith Graph, several snarks, and the complete graph K5 with an additional pendant.

Some of the properties might be familiar. The code for all the properties and invariants can be found here.

Conjecture 1 involves the property, “has_cycle_space_dimension_leq_card_positive_eigenvalues”, namely that the size minus the order plus the number of components of the graph is no more than the number of positive eigenvalues. So Conjecture 1 says that: if a graph is Hamiltonian then either the graph is planar or the size minus the order plus the number of components of the graph is greater than the number of positive eigenvalues. This, of course, seems obscure – but it happens to be true for all 51 Hamiltonian graphs currently known to the program.

Conjecture 2 is that every Hamiltonian graph is either Dirac (the degree of each vertex is at least half the order) or it is not chordal.

Conjecture 3 is that every Hamiltonian graph has radius which is no more than the number of vertices in its center (the set of vertices of minimum eccentricity). Again, this property holds for all 51 Hamiltonian graphs the program knows – and says something more that the two given theoretical bounds.

Conjecture 5 is that every Hamiltonian graph is either Class 1 (the chromatic index equals the maximum degree) or it does not have a perfect matching.

Counterexamples to any of these would be much appreciated and will improve the results of the program.

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