Combinatorially orthogonal matrices and related graphs Original Research Article

Let G be a graph and let c(x,y) denote the number of vertices in G adjacent to both of the vertices x and y. We call G quadrangular if c(x,y) ≠ 1 whenever x and y are distinct vertices in G. Reid and Thomassen proved that E(G) greater-or-equal, slanted 2V(G) −4 for each connected quadrangular graph G, and characterized those graphs for which the lower bound is attained. Their result implies lower bounds on the number of 1ʹs in m × n combinatorially orthogonal (0,1)-matrices, where a (0,1)-matrix A is said to be combinatorially orthogonal if the inner product of each pair of rows and each pair of columns of A is never one. Thus the result of Reid and Thomassen is related to a paper of Beasley, Brualdi and Shader in which they show that a fully indecomposable, combinatorially orthogonal (0,1)-matrix of order n greater-or-equal, slanted 2 has at least 4n − 4 lʹs and characterize those matrices for which equality holds. One of the results obtained here is equivalent to the result of Beasley, Brualdi and Shader. We also prove that E(G) greater-or-equal, slanted 2V(G) − 1 for each connected quadrangular nonbipartite graph G with at least 5 vertices, and characterize the graphs for which the lower bound is attained. In addition, we obtain optimal lower bounds on the number of 1ʹs in m × n combinatorially row-orthogonal (0,1)-matrices.