Geodesic
Embedding arbitrary graphs into strongly regular and distance regular graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 2 (2005), pp. 218-221.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SEMR_2005_2_a13,
     author = {D. G. Fon-Der-Flaass},
     title = {Embedding arbitrary graphs into strongly regular and distance regular graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {218--221},
     publisher = {mathdoc},
     volume = {2},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2005_2_a13/}
}
TY  - JOUR
AU  - D. G. Fon-Der-Flaass
TI  - Embedding arbitrary graphs into strongly regular and distance regular graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2005
SP  - 218
EP  - 221
VL  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2005_2_a13/
LA  - en
ID  - SEMR_2005_2_a13
ER  - 
%0 Journal Article
%A D. G. Fon-Der-Flaass
%T Embedding arbitrary graphs into strongly regular and distance regular graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2005
%P 218-221
%V 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2005_2_a13/
%G en
%F SEMR_2005_2_a13
D. G. Fon-Der-Flaass. Embedding arbitrary graphs into strongly regular and distance regular graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 2 (2005), pp. 218-221. http://geodesic.mathdoc.fr/item/SEMR_2005_2_a13/

[1] A. E. Brouwer, J. H. van Lint, “Strongly regular graphs and partial geometries”, Enumerating and Design, eds. D. M. Jackson, S. A. Vanstone, Academic Press, 1984, 85–122 | MR

[2] G. Exoo, private communication

[3] D. Fon-Der-Flaass, “New prolific constructions of strongly regular graphs”, Adv. Geom., 2 (2002), 301–306 | MR | Zbl

[4] J. Seberry, M. Yamada, “Hadamard matrices, sequences, and block designs”, Contemporary Design Theory, eds. J. H. Dinitz, D. R. Stinson, Wiley, 1992, 431–560 | MR

[5] R. Jajcay, D. Mesner, “Embedding arbitrary finite simple graphs into small strongly regular graphs”, J. Graph Theory, 34 (2000), 1–8 | 3.0.CO;2-E class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[6] V. H. Vu, “On the embedding of graphs into graphs with few eigenvalues”, J. Graph Theory, 22 (1996), 137–149 | 3.0.CO;2-O class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[7] W. D. Wallis, “Construction of strongly regular graphs using affine designs”, Bull. Austr. Math. Soc., 4 (1971), 41–49 | DOI | MR | Zbl