2011/09/02 by Mehrnoush Malekesmaeili, Malekesmaeili, Mehrnoush, Cédric Chauve +3
Computer Science · Engineering · #68R10 #68W40 #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Matrix Theory and Algorithms #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1109.0562
openalex publication_date 2011/09/02 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
A binary matrix has the consecutive ones property (C1P) if it is possible to\norder the columns so that all 1s are consecutive in every row. In [McConnell,\nSODA 2004 768-777] the notion of incompatibility graph of a binary matrix was\nintroduced and it was shown that odd cycles of this graph provide a certificate\nthat a matrix does not have the consecutive ones property. A bound of (k+2) was\nclaimed for the smallest odd cycle of a non-C1P matrix with k columns. In this\nnote we show that this result can be obtained simply and directly via Tucker\npatterns, and that the correct bound is (k+2) when k is even, but (k+3) when k\nis odd.\n