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 M. Marcus and H. Ming, A survey of matrix theory and matrix inequalities, Complementary Series in Math. 14 (1964), 21.
- H. J. Ryser, Matrices with integer elements in combinatorial investigations, Amer. J. Math. 74 (1952), 769–773. MR 50548, DOI 10.2307/2372224
Additional Information
- © Copyright 1991 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 111 (1991), 289-296
- MSC: Primary 05C30; Secondary 05C38, 05C45, 15A15, 15A18
- DOI: https://doi.org/10.1090/S0002-9939-1991-1028288-1
- MathSciNet review: 1028288