Drexel dragonThe Math Forum

The Math Forum Internet Mathematics Library

Counting Hamilton Cycles in Product Graphs

Library Home || Full Table of Contents || Library Help

Visit this site: http://home.wxs.nl/~faase009/counting.html

Author:Frans Faase
Description: 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
Languages: English
Resource Types: Problems/Puzzles, Topic Tools Miscellaneous
Math Topics: Graph Theory, Computer Science

[Privacy Policy] [Terms of Use]

Home || The Math Library || Quick Reference || Search || Help

© 1994- The Math Forum at NCTM. All rights reserved.