Trace-minimal graphs and D-optimal weighing designs

AbstractLet G(v,δ) be the set of all δ-regular graphs on v vertices. Certain graphs from among those in G(v,δ) with maximum girth have a special property called trace-minimality. In particular, all strongly regular graphs with no triangles and some cages are trace-minimal. These graphs play an important role in the statistical theory of D-optimal weighing designs.Each weighing design can be associated with a (0,1)-matrix. Let Mm,n(0,1) denote the set of all m×n (0,1)-matrices and letG(m,n)=maxdetXTX:X∈Mm,n(0,1).A matrix X∈Mm,n(0,1) is a D-optimal design matrix if detXTX=G(m,n). In this paper we exhibit some new formulas for G(m,n) where n≡−1(mod4) and m is sufficiently large. These formulas depend on the congruence class of n(modn). More precisely, let m=nt+r where 0⩽r<n. For each pair n, r, there is a polynomial P(n,r,t) of degree n in t, which depends only on n, r, such that G(nt+r,n)=P(n,r,t) for all sufficiently large t. The polynomial P(n,r,t) is computed from the characteristic polynomial of the adjacency matrix of a trace-regular graph whose degree of regularity and number of vertices depend only on n and r. We obtain explicit expressions for the polynomial P(n,r,t) for many pairs n, r. In particular we obtain formulas for G(nt+r,n) for n=19, 23, and 27, all 0⩽r