Asymptotic Problems in Graph Theory.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1974
- Accession Number
- ADA002076
Entities
People
- E. M. Wright
Organizations
- University of Aberdeen