Trace-minimal graphs and D-optimal weighing designs

Let G(v,δ)G(v,δ) be the set of all δ-regular graphs on v   vertices. Certain graphs from among those in G(v,δ)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)=max{detXTX:X∈Mm,n(0,1)}.G(m,n)=maxdetXTX:X∈Mm,n(0,1).A matrix X ∈ Mm,n(0, 1) is a D-optimal design matrix if det XTX = G(m, n). In this paper we exhibit some new formulas for G(m, n) where n ≡ −1 (mod 4) and m is sufficiently large. These formulas depend on the congruence class of n (mod n). 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 < n, and all sufficiently large t. And we obtain families of formulas for P(n, r, t) from families of trace-minimal graphs including bipartite graphs obtained from finite projective planes, generalized quadrilaterals, and generalized hexagons.