Original version
Discrete Applied Mathematics. 2018, DOI: 10.1016/j.dam.2018.03.024
Abstract
Let A be an n × n (0, ∗)-matrix, so each entry is 0 or ∗. An A-interval matrix is a (0, 1)-matrix obtained from A by choosing some ∗’s so that in every interval of consecutive ∗’s, in a row or column of A, exactly one ∗ is chosen and replaced with a 1, and every other ∗ is replaced with a 0. We consider the existence questions for A-interval matrices, both in general, and for specific classes of such A defined by permutation matrices. Moreover, we discuss uniqueness and the number of A-permutation matrices, as well as properties of an associated graph.