# zbMATH — the first resource for mathematics

Embedding arbitrary graphs into strongly regular and distance-regular graphs. (English) Zbl 1094.05057
Summary: 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.
##### MSC:
 5e+30 Association schemes, strongly regular graphs
Full Text: