ERIC Number: EJ992902
Record Type: Journal
Publication Date: 2012
Pages: 8
Abstractor: As Provided
ISBN: N/A
ISSN: ISSN-0020-739X
EISSN: N/A
Constructing Dense Graphs with Unique Hamiltonian Cycles
Lynch, Mark A. M.
International Journal of Mathematical Education in Science and Technology, v43 n3 p388-395 2012
It is not difficult to construct dense graphs containing Hamiltonian cycles, but it is difficult to generate dense graphs that are guaranteed to contain a unique Hamiltonian cycle. This article presents an algorithm for generating arbitrarily large simple graphs containing "unique" Hamiltonian cycles. These graphs can be turned into dense graphs which are guaranteed to be not Hamiltonian by the removal of an edge from the cycle. The generated graphs are dense in the sense that average vertex degree of the graphs is just greater than half the number of vertices in the graph. (Contains 6 figures.)
Descriptors: Mathematics Instruction, Teaching Methods, Graphs, Vocabulary, Validity, Mathematical Logic
Taylor & Francis, Ltd. 325 Chestnut Street Suite 800, Philadelphia, PA 19106. Tel: 800-354-1420; Fax: 215-625-2940; Web site: http://www.tandf.co.uk/journals
Publication Type: Journal Articles; Reports - Descriptive
Education Level: N/A
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A
Grant or Contract Numbers: N/A