5
$\begingroup$

Given a random graph by the Erdős–Rényi model, if the minimal node degree is greater than 1 (or $\geq 2$), or randomly select a graph from the graphs with node degrees greater than 1 ($\geq 2$), what's the probability for it to be a Hamiltonian graph?

$\endgroup$
6
$\begingroup$

The probability that a random graph with $n$ nodes and $cn\log n$ edges contains a Hamiltonian circuit tends to $1$ as $n\rightarrow\infty$ (and for sufficiently large $c$) (Pósa 1976). Since an ER random graph has $\Omega(n^2)$ edges, it is almost certainly Hamiltonian as $n\rightarrow \infty$, even without the constraint on the minimal degree.

$\endgroup$
  • 2
    $\begingroup$ However, if the edge number of a random graph with $n$ nodes is ($n$/2)(log$n$ + log log$n$ + $c$), then the probability for it to be Hamiltonian is exp(-exp(-$c$)) (Komlos and Szemeredi 1983). So, it is interesting to know the Hamiltonian probability if the edge number of a random graph is less than $cn$log$n$ and the node degrees are greater than 1. $\endgroup$ – winston Nov 6 '14 at 11:10

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.