A structure theorem for the consecutive 1's property

Alan Tucker

doi:10.1016/0095-8956(72)90019-6

A structure theorem for the consecutive 1's property

Alan Tucker

Applied Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

109 Scopus citations

Abstract

A (0, 1)-matrix M has the consecutive 1's property for columns if the rows of M can be permuted so that the 1's in each column appear consecutively. A graph-theoretic approach is used to characterize matrices with this property in terms of forbidden submatrices. Graphs whose adjacency matrix has this property are also characterized.

Original language	English
Pages (from-to)	153-162
Number of pages	10
Journal	Journal of Combinatorial Theory, Series B
Volume	12
Issue number	2
DOIs	https://doi.org/10.1016/0095-8956(72)90019-6
State	Published - Apr 1972

Access to Document

10.1016/0095-8956(72)90019-6

Cite this

@article{658db672e51645e39143c10d78c88119,

title = "A structure theorem for the consecutive 1's property",

abstract = "A (0, 1)-matrix M has the consecutive 1's property for columns if the rows of M can be permuted so that the 1's in each column appear consecutively. A graph-theoretic approach is used to characterize matrices with this property in terms of forbidden submatrices. Graphs whose adjacency matrix has this property are also characterized.",

author = "Alan Tucker",

year = "1972",

month = apr,

doi = "10.1016/0095-8956(72)90019-6",

language = "English",

volume = "12",

pages = "153--162",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

number = "2",

}

TY - JOUR

T1 - A structure theorem for the consecutive 1's property

AU - Tucker, Alan

PY - 1972/4

Y1 - 1972/4

N2 - A (0, 1)-matrix M has the consecutive 1's property for columns if the rows of M can be permuted so that the 1's in each column appear consecutively. A graph-theoretic approach is used to characterize matrices with this property in terms of forbidden submatrices. Graphs whose adjacency matrix has this property are also characterized.

AB - A (0, 1)-matrix M has the consecutive 1's property for columns if the rows of M can be permuted so that the 1's in each column appear consecutively. A graph-theoretic approach is used to characterize matrices with this property in terms of forbidden submatrices. Graphs whose adjacency matrix has this property are also characterized.

UR - https://www.scopus.com/pages/publications/0011610992

U2 - 10.1016/0095-8956(72)90019-6

DO - 10.1016/0095-8956(72)90019-6

M3 - Article

AN - SCOPUS:0011610992

SN - 0095-8956

VL - 12

SP - 153

EP - 162

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

A structure theorem for the consecutive 1's property

Abstract

Access to Document

Other files and links

Fingerprint

Cite this