R. Merris, Single-hook characters and Hamiltonian circuits, Linear & Multilinear Algebra 14 (1983), 21-35. Research supported by NSF grant MCS 77-28437. AMS Abstracts 3 (1982), 130. Math Reviews 85i:20016.

This article involves Kostka coefficients, Schur polynomials, immanants, and graph theory. The connecting thread is the notion of a single-hook character of the symmetric group. A typical result is this: Let G be a graph on n vertices. The Laplacian matrix, L(G) =D(G) - A(G), where D(G) is the diagonal matrix of vertex degrees and A(G) is the adjacency matrix. If d_r is the immanant afforded by S_n and the irreducible character corresponding to the partition [r,1^(n-r)], then the number of hamiltonian circuits (cycles) in G is h(G) = [d_2(L(G)) - d_3(L(G)) + ... + (-1)^n d_n(L(G))]/2n. Among the publications citing the paper are

  • R. Grone, Linear Algebra Appl. 68 (1985), 252-254.
  • W. Hartman, Linear & Multilinear Algebra 18 (1985), 127-140.
  • J. R. Stembridge, Canad. J. Math. 44 (1992), 1079-1099.
  • O. Chan and T. K. Lam, Linear Algebra Appl. 261 (1997), 23-47.
  • O. Chan and T. K. Lam, SIAM J. Matrix Anal. Appl. 21 (1999), 129-144.
  • P. Burgisser, SIAM J. Computing 30 (2000), 1023-1040.
  • Gi-Sang Cheon and Ian M. Wanless, Linear Algebra Appl. (2005), 314-342.