Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T14:18:56.392Z Has data issue: false hasContentIssue false
  • English
  • Français

Large cycles in large labelled graphs. II

Published online by Cambridge University Press:  24 October 2008

E. M. Wright
E. M. Wright
Affiliation:
University of Aberdeen
Get access Rights & Permissions [Opens in a new window]

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Erdös, P. and Renyi, A.On the evolution of random graphs. Publ. Math. Inst. Hungarian Acad. Sci. 5 (1960), 17–61.Google Scholar
(2)Wright, E. M.Large cycles in large labelled graphs. Math. Proc. Cambridge Philos. Soc. 78 (1975), 7–17.CrossRefGoogle Scholar