Authors’ abstract: Let \({\mathcal G}(v, \delta)\) be the set of all \(\delta\)-regular graphs on \(v\) vertices. Certain graphs from among those in \({\mathcal G}(v,\delta)\) 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 \(M_{m,n}(0,1)\) denote the set of all \(m\times n\) \((0,1)\)-matrices and let \[ G(m,n) = \max\{\det X^T X : X\in M_{m,n}(0,1)\}. \] A matrix \(X\in M_{m,n}(0,1)\) is a \(D\)-optimal design matrix if \(\det X^T X = G(m,n)\). We exhibit some new formulas for \(G(m,n)\) where \(n\equiv -1\pmod 4\) and \(m\) is sufficiently large. These formulas depend on the congruence class of \(m\pmod n\). More precisely, let \(m=nt+r\) where \(0\leq 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\leq 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.