THE EXISTENCE AND GENERATION OF A HAMILTON CIRCUIT IN A TREE GRAPH.
Abstract
The existence of a Hamilton circuit in a tree graph was first proved by R. L. Cummins in his Ph. D. thesis at the University of Illinois. However, the proof involves complicated procedures, and it is hard to apply it to the generation of all the trees in a given graph. The new proof, which is straightforward and concise, is given in this paper. This proof is constructive and applicable to the generation of all the trees in a given graph. A general procedure for obtaining a Hamilton circuit in a tree graph is shown. By applying this procedure, all the trees in a graph with 5 vertices and 8 edges are generated in an example. The procedure is of recursive nature and hence suitable for computation by a digital computer. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1966
- Accession Number
- AD0640542
Entities
People
- Takahiko Kamae
Organizations
- University of Illinois Urbana–Champaign