Geodesic
The number of sparsely edged labelled Hamiltonian graphs
Glasgow mathematical journal, Tome 24 (1983) no. 1, pp. 83-87

Voir la notice de l'article provenant de la source Cambridge University Press

An (n, q) graph is a graph on n labelled points and q lines, no loops and no multiple lines. We write N = 1⁄2n(n – 1), B(a, b) = a!/{b!(a – b)!} and B(a, 0) = 1, so that there are just B(N, q)different (n, q) graphs. Again h(n, q) is the number of Hamiltonian (n, q) graphs. Much attention has been devoted to the problem of determining for which q = q(n) “almost all” (n, q) graphs are Hamiltonian, i.e. for which q we haveas n → ∞. I proved [8, Theorem 4] that qn–3/2; → ∞ is a sufficient condition by showing that, for such q, almost all (n, q) graphs have about the average number of Hamiltonian circuits (H.c.s). 
Wright, E. M. The number of sparsely edged labelled Hamiltonian graphs. Glasgow mathematical journal, Tome 24 (1983) no. 1, pp. 83-87. doi: 10.1017/S0017089500005097
@article{10_1017_S0017089500005097,
     author = {Wright, E. M.},
     title = {The number of sparsely edged labelled {Hamiltonian} graphs},
     journal = {Glasgow mathematical journal},
     pages = {83--87},
     year = {1983},
     volume = {24},
     number = {1},
     doi = {10.1017/S0017089500005097},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/S0017089500005097/}
}
TY  - JOUR
AU  - Wright, E. M.
TI  - The number of sparsely edged labelled Hamiltonian graphs
JO  - Glasgow mathematical journal
PY  - 1983
SP  - 83
EP  - 87
VL  - 24
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/S0017089500005097/
DO  - 10.1017/S0017089500005097
ID  - 10_1017_S0017089500005097
ER  - 
%0 Journal Article
%A Wright, E. M.
%T The number of sparsely edged labelled Hamiltonian graphs
%J Glasgow mathematical journal
%D 1983
%P 83-87
%V 24
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/S0017089500005097/
%R 10.1017/S0017089500005097
%F 10_1017_S0017089500005097

[1] 1.Cayley, A., A theorem on trees, Quart. J. Math. 23 (1889), 376–378. Google Scholar

[2] 2.Erdös, P. and Rényi, A., On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 5 (1960), 17–61; reprinted in P. Erdös, The art of counting (M.I.T. Press, 1973), 574–617. Google Scholar

[3] 3.Erdös, P. and Rényi, A., On the strength of connectedness of a random graph, Ada Math. Acad. Set. Hungar. 12 (1961), 261–267; reprinted in P. Erdös, The art of counting (M.I.T. Press, 1973), 618–624. Google Scholar | DOI

[4] 4.Gray, P. M. D., Murray, A. M. and Young, N. A., Wright's formulae for the number of connected sparsely edged graphs, J. Graph Theory 1 (1977), 331–334. Google Scholar | DOI

[5] 5.Koršnov, A. D., Solution of a problem of Erdös and Rényi on Hamiltonian cycles in nonoriented graphs, Soviet Math. Dokl. 17 (1976), 760–764; (Dokl. Akad. Nauk SSSR (1976), no. 3, 529–532). Google Scholar

[6] 6.Moon, J. W., Various proofs of Cayley's formula for counting trees, A seminar on graph theory, ed. Harary, F. (Holt, Rinehart and Winston, 1967), 70–78. Google Scholar

[7] 7.Rényi, A., On connected graphs I, Magyar Tud. Akad. Mat. Kutató Int. Közl. 4 (1959), 385–388. Google Scholar

[8] 8.Wright, E. M., For how many edges is a graph almost certainly Hamiltonian?, J. London Math. Soc. (2) 8 (1974), 44–48. Google Scholar | DOI

[9] 9.Wright, E. M., The number of connected sparsely edged graphs, J. Graph Theory 1 (1977), 317–330. Google Scholar | DOI

[10] 10.Wright, E. M., The number of connected sparsely edged graphs. II. Smooth graphs and blocks, J. Graph Theory 2 (1978), 299–305. Google Scholar | DOI

[11] 11.Wright, E. M., The number of connected sparsely edged graphs. III. Asymptotic results, J. Graph Theory 4 (1980), 393–407. Google Scholar | DOI

Cité par Sources :