AN EXTENSION OF A THEOREM OF FULKERSON AND GROSS

Fulkerson and Gross proved a theorem regarding 0-1 matrices that have the consecutive ones property. They then used it to test for this prop erty for a given matrix. This was extended to matrices with the circul ar ones property by Tucker. It was further extended to the one drop pr operty, which occurs in integer programming problems that arise in sch eduling. When this result was presented, the question was raised wheth er there is a hierarchy of such properties and theorems. This paper an swers this question in the affirmative. These results may help in test ing matrices for these properties and also in solving these integer pr ograms.