On a Class of Graphic Matrices

Abstract

A $\{0,1\}$-matrix $M$ is tree graphic if there exists a tree $T$ such that the edges of $T$ are indexed on the rows of $M$ and the columns are the incidence vectors of the edge sets of paths of $T$. Analogously, $M$ is ditree graphic if there exists a ditree $T$ such that the directed edges of $T$ are indexed on the rows of $M$ and the columns are the incidence vectors of the directed-edge sets of dipaths of $T$. In this paper, a simple proof of an excluded-minor characterization of the class of tree-graphic matrices that are ditree-graphic is given. Then, using the same proof technique, a characterization of a “special” class of tree-graphic matrices (which are contained in the class of consecutive $1$’s matrices) is stated and proved.