|
Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2005, Volume 2, Pages 218–221
(Mi semr26)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Research papers
Embedding arbitrary graphs into strongly regular and distance regular graphs
D. G. Fon-Der-Flaass Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
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.
Received October 4, 2005, published November 3, 2005
Citation:
D. G. Fon-Der-Flaass, “Embedding arbitrary graphs into strongly regular and distance regular graphs”, Sib. Èlektron. Mat. Izv., 2 (2005), 218–221
Linking options:
https://www.mathnet.ru/eng/semr26 https://www.mathnet.ru/eng/semr/v2/p218
|
|