Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T21:09:55.710Z Has data issue: false hasContentIssue false
  • English
  • Français

Almost all Graphs have a Spanning Cycle

Published online by Cambridge University Press:  20 November 2018

J. W. Moon
J. W. Moon*
Affiliation:
University of Cape Town, Cape Province, South Africa
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A graph is a collection of nodes some pairs of which are joined by a single edge. A k-path, or a path of length k, is a sequence of nodes {p1 p2,… Pk+1} such that Pi is joined to pi+1 for 1 ≤i≤k; we assume the nodes are distinct except that p1 and pk+1 may be the same in which case we call the path a k-cycle or a cycle of length k. (Notice that two nodes joined by an edge determine a 2-cycle according to this definition; it will also be convenient to regard a single node as a 1-cycle.) A spanning path or cycle is one that involves every node of the graph. One of the unsolved problems of graph theory is to characterize those graphs that have a spanning path or cycle.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 15 , Issue 1 , March 1972 , pp. 39 - 41
Copyright
Copyright © Canadian Mathematical Society 1972

References

1. Erdös, P. and Rényi, A., On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutatö Int. Közl. 5 (1970), 17-61.Google Scholar