A graph is called maximally non-hamiltonian, if it does not contain a hamilton-cycle, but no edge can be added without creating a hamilton-cycle. In other words, every pair of non-adjacent vertices $(u/v)$ can be connected with a hamiltonian path.

  • How can the maximally non-hamiltonian graphs be classified with known graph properties ?
  • $\begingroup$ OEIS states that the number of maximally non-hamiltonian graphs with $1,2,3,4,5,6,7,8,9,10$ vertices is $0,1,1,1,3,3,7,9,18,31$. Can someone enumerate these graphs and list those with maximum degree $<n-1$, if n is the number of vertices ? $\endgroup$ – Peter Oct 14 '14 at 11:27

Using the edge count. If there is a non-Hamiltonian graph $G$ on $n$ vertices, the maximal number of edges that $G$ can contain is ${n-1\choose 2} +1 = {n\choose 2} - (n-2).$

  • $\begingroup$ This is confusing. The maximum number of edges in a graph with $n$ vertices is $\binom{n}{2}$. Perhaps you are trying to argue something about edges of a special kind of graph, like discussed in the Question. But your one-line answer fails to make such a connection clear. $\endgroup$ – hardmath Feb 20 '16 at 18:23
  • $\begingroup$ The question refers to non-Hamiltonian graphs. What I've written is true for such a graph. I will edit my response. $\endgroup$ – Henry Feb 20 '16 at 18:51
  • $\begingroup$ So are you saying that maximally non-hamiltonian graphs can be classified by counting the number of edges? Does this tell us how many (up to isomorphism) maximally non-hamiltonian graphs on $5$ vertices there are? $\endgroup$ – hardmath Feb 20 '16 at 19:06
  • $\begingroup$ There is a unique Extremal graph with the number of edges I listed on $n$ vertices so that there is no Hamilton cycle. Many graphs with fewer edges are not Hamiltonian, but they will not be maximally so. $\endgroup$ – Henry Mar 3 '16 at 20:52
  • $\begingroup$ If your claim that the extremal graph was unique were true, then counting edges would work to classify them (as would counting the vertices). But the OP has referenced OEIS sequence A185306, according to which there are three distinct maximally non-Hamiltonian graphs on $5$ vertices. $\endgroup$ – hardmath Mar 3 '16 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.