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

Abstract

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 + I, where A is the adjacency matrix of G, I is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g (G) ≥ 5 has a Hamiltonian circuit if and only if the matrix A + I can be permuted on rows such that each column has at most (or exactly) k - 1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k - 1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A + I can be permuted on rows to have at most (or exactly) k - 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 = 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 ≥ 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 ≥ 2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row. © 2007 Elsevier B.V. All rights reserved.