Large cycles in large labelled graphs. II
Published online by Cambridge University Press: 24 October 2008
Extract
1. This paper is a sequel to (2). The notation is the same and we assume the reader to be familiar with that paper. We there proved various theorems which established conditions under which ‘almost all’ labelled (n, q) graphs contained a k-cycle, i.e. under which the proportion of all labelled (n, q) graphs which contained a k-cycle tended to 1 as n → ∞. We here consider a different but related problem. If a graph contains a cycle of length k for every k such that 3 ≤ k ≤ k0, we say that the graph is pancyclic up to k0. We find conditions on k0, n and q such that almost all (n, q) graphs are pancyclic up to k0. If k0 = 0(1), the result follows trivially from Theorem 3a of (1) (Theorem 1 of (2)), but if k0 → ∞with n the matter is not so simple. We shall prove the following theorem.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 81 , Issue 1 , January 1977 , pp. 1 - 2
- Copyright
- Copyright © Cambridge Philosophical Society 1977
References
REFERENCES
- 3
- Cited by