Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices

We show that the Hamiltonicity of a regular graph G   can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+IA+I, where AA is the adjacency matrix of G  , II is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G   with girth g(G)⩾5g(G)⩾5 has a Hamiltonian circuit if and only if the matrix A+IA+I can be permuted on rows such that each column has at most (or exactly) k-1k-1 circular blocks of consecutive ones; and if the graph G is k  -regular except for two (k-1)(k-1)-degree vertices a and b, then there is a Hamiltonian path from a to b   if and only if the matrix A+IA+I can be permuted on rows to have at most (or exactly) k-1k-1 linear blocks per column.Then we turn to the problem of determining whether a given matrix can have at most k   blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k=1k=1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255–265]; Flammini et al. showed its NP-completeness for general k   [Algorithmica 16 (1996) 549–568]; and Goldberg et al. proved the same for every fixed k⩾2k⩾2 [J. Comput. Biol. 2 (1) (1995) 139–152]. In this paper, we strengthen their result by proving that the problem remains NP-complete for every constant k⩾2k⩾2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row.