0
$\begingroup$

A Hamiltonian graph contains a Hamiltonian cycle. A non-Hamiltonian does not contain any Hamiltonian cycle. For every positive integer n are there more non-Hamiltonian graph than Hamiltonian on n vertices?

I found this link:

Maximum number of edges in a non-Hamiltonian graph

Maybe this could be useful

$\endgroup$
  • 1
    $\begingroup$ I think you mean to say, "For every positive integer $n$ are there more ..." What are your thoughts on this? What have you done so far? $\endgroup$ – saulspatz Aug 30 '18 at 14:35
  • 2
    $\begingroup$ Take a look at Probability of choosing a random graph with a Hamilton cycle $\endgroup$ – saulspatz Aug 30 '18 at 14:45
  • 2
    $\begingroup$ Yes, it means that as $n$ goes to infinity, almost all the $n-$vertex graphs (labeled graphs, actually) are Hamiltonian. $\endgroup$ – saulspatz Aug 30 '18 at 15:46
  • 1
    $\begingroup$ My last comment wasn't very good. When $p=\frac12,$ every labelled graph has the same probability of being chosen, so the probability that a labeled graph is Hamiltonian is equal to the fraction of labeled graphs that are Hamiltonian. $\endgroup$ – saulspatz Aug 30 '18 at 16:04
  • 1
    $\begingroup$ @saulspatz Almost all random graphs have trivial automorphism group. (See, e.g., Theorem 3.1 in this paper, or earlier Theorem 2 in this paper.) So any w.h.p. result about $G(n,\frac12)$ extends to a result about almost all unlabeled graphs. $\endgroup$ – Misha Lavrov Aug 30 '18 at 18:25
1
$\begingroup$

OEIS A003216 gives the number of Hamiltonian graphs on $n$ points. No formula is given, but $a(8)=6196$ says there are $6196$ Hamiltonian graphs on $8$ points. OEIS A000088 gives the total number of graphs on $n$ unlabeled points. For $8$ points there are $12346$ so just over half the graphs on $8$ points are Hamiltonian. For $12$ points, the highest in the Hamiltonian list, there are $152522187830$ Hamiltonian graphs out of $165091172592$ which would claim that over $92\%$ of the $12$ point graphs are Hamiltonian.

For $n=2$ there are two graphs, neither of which is Hamiltonian. For $n \lt 8$ over half the graphs are not Hamiltonian. It doesn't seem surprising to me that once $n$ gets large most graphs are Hamiltonian. If you think about the complete graph on $n$ vertices you need very few of the edges to make a Hamiltonian path.

$\endgroup$

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.