Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)


For how many edges is a digraph almost certainly Hamiltonian?

Author: E. M. Wright
Journal: Proc. Amer. Math. Soc. 41 (1973), 384-388
MSC: Primary 05C35
MathSciNet review: 0342436
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C35

Retrieve articles in all journals with MSC: 05C35

Additional Information

PII: S 0002-9939(1973)0342436-7
Keywords: Digraph, Hamiltonian cycle
Article copyright: © Copyright 1973 American Mathematical Society