Associated Graphs of \(p\)-Dimensional \((0,1)\)-Matrices

Abstract

The \(associated \;graph \;of\; a\) \((0,1)\)-\(matrix\) has as its vertex set the lines of the matrix with vertices adjacent whenever their lines intersect at \(a\) \(1\). This association relates the \((0,1)\)-matrix and bipartite graph versions of the König-Egervary Theorem. We extend this graph association to higher dimensional matrices. We characterize these graphs, modulo isolated vertices, using a coloring in which every path between each pair of vertices contains the same two colors. We rely on previous results about \(p\)-dimensional gridline graphs, where vertices are \(1\)’s in a higher dimensional matrix and vertices are adjacent whenever they are on a common line. Also important is the dual property that the doubly iterated clique graph of a diamond- and simplicial vertex-free graph is isomorphic to the original.