Counting Hamilton Cycles in Product Graphs
Library Home || Full Table of Contents || Library Help
|Exploration of Hamilton paths through a program which draws a snake that starts at one place in a box, and then extends itself until it cannot go further, after which it shrinks again, to seek another path. The author coded these snake programs in Fortran, C, Acorn Atom, Turbo PASCAL, and Maple, and ultimately reported his findings in a paper that has been published in Ars Combinatoria, Volume XLIX, August 1998 under the title "On the number of specific spanning subgraphs of the graphs G x P_n." Extensions to a general case of the product of any graph with P_n (and counting Hamilton paths, 2-factors and other things), integer sequences, the chess/rook.path problem, spanning trees, labyrinths, domino tilings, paths from one corner to another|
|Levels:||High School (9-12), College, Research|
|Resource Types:||Problems/Puzzles, Topic Tools Miscellaneous|
|Math Topics:||Graph Theory, Computer Science|
© 1994- The Math Forum at NCTM. All rights reserved.