Asymptotic Problems in Graph Theory.
Final technical rept. 1 Dec 73-30 Nov 74,
ABERDEEN UNIV (SCOTLAND)
Pagination or Media Count:
An n,q graph is one with n nodes and q edges. It is shown that the asymptotic probability that an n,q graph is Hamiltonian is the same whether it is labelled or unlabelled. Again the strict probability for the unlabelled case can decrease as q increases in a certain interval, but not for the labelled case. Dr. Sheehan and the author find a general formula for the number of Hamiltonian circuits in a thickly-edged graph two very special cases of this were known. The use of the Exclusion-Inclusion Theorem to find asymptotic results can be extended more widely than had previously seemed possible. A detailed theory of the appearance of large cycles in large labelled graphs is developed. From this and other results there follows the somewhat paradoxical evolution of the unlabelled graph as the number of edges increases.
- Statistics and Probability