COMBINATORIALLY ORTHOGONAL MATRICES AND RELATED GRAPHS

Let G be a graph and let c(x,y) denote the number of vertices in G adj acent to both of the vertices x and y. We call G quadrangular if c(x,y ) not equal 1 whenever x and y are distinct vertices in G. Reid and Th omassen proved that \E(G)\ greater than or equal to 2\V(G)\ - 4 for ea ch connected quadrangular graph G, and characterized those graphs for which the lower bound is attained. Their result implies lower bounds o n the number of 1's in m x n combinatorially orthogonal (0,1)-matrices , where a (0,1)-matrix A is said to be combinatorially orthogonal if t he 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 pape r of Beasley, Brualdi and Shader in which they show that a fully indec omposable, combinatorially orthogonal (0,1)-matrix of order n greater than or equal to 2 has at least 4n - 4 1's and characterize those matr ices for which equality holds. One of the results obtained here is equ ivalent to the result of Beasley, Brualdi and Shader. We also prove th at \E(G)\ greater than or equal to 2\V(G)\ - 1 for each connected quad rangular nonbipartite graph G with at least 5 vertices, and characteri ze the graphs for which the lower bound is attained. In addition, we o btain optimal lower bounds on the number of 1's in m x n combinatorial ly row-orthogonal (0,1)-matrices. (C) 1998 Elsevier Science Inc. All r ights reserved.