Enumeration of Hamiltonian cycles and paths in a graph

Author:
C. J. Liu

Journal:
Proc. Amer. Math. Soc. **111** (1991), 289-296

MSC:
Primary 05C30; Secondary 05C38, 05C45, 15A15, 15A18

MathSciNet review:
1028288

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**[1]**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**, 10.1137/0605038**[2]**Frank Harary and Edgar M. Palmer,*Graphical enumeration*, Academic Press, New York-London, 1973. MR**0357214****[3]**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**, 10.1016/S0195-6698(81)80004-2**[4]**M. Marcus and H. Ming,*A survey of matrix theory and matrix inequalities*, Complementary Series in Math.**14**(1964), 21.**[5]**H. J. Ryser,*Matrices with integer elements in combinatorial investigations*, Amer. J. Math.**74**(1952), 769–773. MR**0050548**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
05C30,
05C38,
05C45,
15A15,
15A18

Retrieve articles in all journals with MSC: 05C30, 05C38, 05C45, 15A15, 15A18

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9939-1991-1028288-1

Article copyright:
© Copyright 1991
American Mathematical Society