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: is the number of those Hamiltonian cycles in the complete digraph on nodes, each of which has just edges in common with a particular Hamiltonian cycle, and . We show that and deduce that for large and that if . An digraph is one with labelled nodes and edges. From the result for , we deduce that, if as , then almost all digraphs are Hamiltonian. If as , then the proportion of digraphs which are non-Hamiltonian is at most as .

**[1]**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.**[2]**Patrick Eugene O’Neil,*Asymptotics in random (𝑂,1)-matrices*, Proc. Amer. Math. Soc.**25**(1970), 290–296. MR**0255430**, 10.1090/S0002-9939-1970-0255430-9**[3]**I. Palásti,*On the common edges of Hamilton-cycles of a complete linear graph*, Combinatorial theory and its applications, III (Proc. Colloq., Balatonfüred, 1969) North-Holland, Amsterdam, 1970, pp. 829–868. MR**0297612**

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

Retrieve articles in all journals with MSC: 05C35

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9939-1973-0342436-7

Keywords:
Digraph,
Hamiltonian cycle

Article copyright:
© Copyright 1973
American Mathematical Society