Vol. 15, No. 3, 1965

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Vol. 321: 1  2
Vol. 320: 1  2
Online Archive
The Journal
Editorial Board
Submission Guidelines
Submission Form
Policies for Authors
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
Other MSP Journals
Incidence matrices and interval graphs

Delbert Ray Fulkerson and Oliver Gross

Vol. 15 (1965), No. 3, 835–855

According to present genetic theory, the fine structure of genes consists of linearly ordered elements. A mutant gene is obtained by alteration of some connected portion of this structure. By examining data obtained from suitable experiments, it can be determined whether or not the blemished portions of two mutant genes intersect or not, and thus intersection data for a large number of mutants can be represented as an undirected graph. If this graph is an “interval graph,” then the observed data is consistent with a linear model of the gene.

The problem of determining when a graph is an interval graph is a special case of the following problem concerning (0,1)-matrices: When can the rows of such a matrix be permuted so as to make the 1’s in each column appear consecutively? A complete theory is obtained for this latter problem, culminating in a decomposition theorem which leads to a rapid algorithm for deciding the question, and for constructing the desired permutation when one exists.

Mathematical Subject Classification
Primary: 92.20
Secondary: 05.25
Received: 21 April 1964
Published: 1 September 1965
Delbert Ray Fulkerson
Oliver Gross