A strongly regular \(n\)-full graph of small order (Q1924497)

A graph is \(n\)-full if it contains every graph of order \(n\) as an induced subgraph. By a theorem of \textit{J. W. Moon} (who used the term \(n\)-universal, rather than \(n\)-full) [On minimal \(n\)-universal graphs, Proc. Glasg. Math. Assoc. 7, 32-33 (1965; Zbl 0132.21202)] it is known that \(\lambda(n)\)---the smallest positive integer \(N\) for which there exists an \(n\)-universal graph on \(N\) vertices---satisfies the inequalities \(2^{{n-1\over 2}}\leq\lambda(n)\leq cn\cdot 2^{{n-1\over 2}}\) where \(c\leq \sqrt{9/8}\); the author cites a weaker right inequality proved by \textit{B. Bollobás} and \textit{A. Thomason} [Graphs which contain all small graphs, Eur. J. Comb. 2, 13-15 (1981; Zbl 0471.05037)]. Bollobás and Thomason proved that, for prime powers \(q\) such that \(q\equiv 1\text{ mod }4\), and \(q\geq(2^{n-2}(n-1)+1)^2\), the strongly regular ``Paley'' graph \(Q_q\)---whose vertices are all elements of \(\text{GF}(q)\), two of which are adjacent iff their difference is a square---is \(n\)-full. \(V^n_{P_0}\) is the \(n\)-dimensional vector space over \(\text{GF}(2)\) with inner product \(P_0({\mathbf a},{\mathbf b})=a_1b_n+a_2b_{n-1}+\cdots+a_nb_1\), where \({\mathbf a}=(a_1,a_2,\dots,a_n)\), \({\mathbf b}=(b_1,b_2,\dots,b_n)\); \(G(V^n_{P_0})\) is the graph whose vertices are the vectors in \(V^n_{P_0}\), with \({\mathbf a}\) and \({\mathbf b}\) adjacent iff \(P_0({\mathbf a},{\mathbf b})=1\). The author observes that \(G(V^n_{P_0})\) is strongly regular. Theorem 1. For every positive integer \(k\), the graph \(G(V^{2k}_{P_0})\) is \((2k-1)\)-full. This implies the following improvement of the result of Bollobás and Thomason: For every positive integer \(n\) there is a strongly regular \(n\)-full graph of order at most \(2^{n+2}\). From the author's introduction: In addition we (\dots) show that the estimation on the fullness of our graph is best possible (Theorem 2). So it requires new method (sic) to construct a strongly regular \(n\)-full graph with order closer to the lower bound. Nevertheless, even the existence of such graph (sic) is not clear.