×

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:
05E30 Association schemes, strongly regular graphs
PDF BibTeX XML Cite
Full Text: EuDML