For how many edges is a digraph almost certainly Hamiltonian?
HTML articles powered by AMS MathViewer
- by E. M. Wright
- Proc. Amer. Math. Soc. 41 (1973), 384-388
- DOI: https://doi.org/10.1090/S0002-9939-1973-0342436-7
- PDF | Request permission
Abstract:
${K_n}(r)$ is the number of those Hamiltonian cycles in the complete digraph on $n$ nodes, each of which has just $r$ edges in common with a particular Hamiltonian cycle, and $B(n,r) = n!/\{ r!(n - r)!\}$. We show that ${K_n}(r) = B(n,r){K_{n - r}}(0)$ and deduce that ${K_n}(0)\sim (n - 1)!{e^{ - 1}}$ for large $n$ and that ${K_n}(r)\sim (n - 1)!{e^{ - 1}}/r!$ if $r = 0(n)$. An $(n,q)$ digraph is one with $n$ labelled nodes and $q$ edges. From the result for ${K_n}(r)$, we deduce that, if $q{n^{ - 3/2}} \to \infty$ as $n \to \infty$, then almost all $(n,q)$ digraphs are Hamiltonian. If $q{n^{ - 3/2}} \to c$ as $n \to \infty$, then the proportion of $(n,q)$ digraphs which are non-Hamiltonian is at most $1 - \exp ( - {c^{ - 2}})$ as $n \to \infty$.References
- L. Euler, Calcul de la probabilité dans le jeu de rencontre, Mém. Acad. Sci. Berlin 7 (1753), 255-270; Opera omnia (1) 7 (1923), 11-25.
- Patrick Eugene O’Neil, Asymptotics in random $(O,\,1)$-matrices, Proc. Amer. Math. Soc. 25 (1970), 290–296. MR 255430, DOI 10.1090/S0002-9939-1970-0255430-9
- I. Palásti, On the common edges of Hamilton-cycles of a complete linear graph, Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969) North-Holland, Amsterdam, 1970, pp. 829–868. MR 0297612
Bibliographic Information
- © Copyright 1973 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 41 (1973), 384-388
- MSC: Primary 05C35
- DOI: https://doi.org/10.1090/S0002-9939-1973-0342436-7
- MathSciNet review: 0342436