Enumeration of Hamiltonian cycles and paths in a graph

Liu, C. J.

doi:10.1090/S0002-9939-1991-1028288-1

Enumeration of Hamiltonian cycles and paths in a graph
HTML articles powered by AMS MathViewer

by C. J. Liu PDF

Proc. Amer. Math. Soc. 111 (1991), 289-296 Request permission

Abstract:

First, we show that the determinant of a given matrix can be expanded by its principal minors together with a set of arbitrary parameters. The enumeration of Hamiltonian cycles and paths in a graph is then carried out by an algebraic method. Three types of nonalgebraic representation are formulated. The first type is given in terms of the determinant and permanent of a parametrized adjacent matrix. The second type is presented by a determinantal function of multivariables, each variable having domain 0, 1. Formulas of the third type are expressed by spanning trees of subgraphs. When applying the formulas to a complete multipartite graph, one can easily find the results.

References

C. J. Liu and Yutze Chow, On operator and formal sum methods for graph enumeration problems, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 384–406. MR 752043, DOI 10.1137/0605038
Frank Harary and Edgar M. Palmer, Graphical enumeration, Academic Press, New York-London, 1973. MR 0357214
I. P. Goulden and D. M. Jackson, The enumeration of directed closed Euler trails and directed Hamiltonian circuits by Lagrangian methods, European J. Combin. 2 (1981), no. 2, 131–135. MR 622078, DOI 10.1016/S0195-6698(81)80004-2

A survey of matrix theory and matrix inequalities

14

H. J. Ryser, Matrices with integer elements in combinatorial investigations, Amer. J. Math. 74 (1952), 769–773. MR 50548, DOI 10.2307/2372224