Аннотация:
We show that every simple graph on x vertices is an induced subgraph of some strongly regular graph on fewer than $4x^2$ vertices; which, up to a constant factor, coincides with the existing lower bound. We also show that every simple graph on $x$ vertices is an induced subgraph of some distance regular graph of diameter $3$ on fewer than $8x^3$ vertices, and every simple bipartite graph on $x$ vertices is an induced subgraph of some distance regular bipartite graph of diameter $3$ on fewer than $8x^2$ vertices.