RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2005 Volume 2, Pages 218–221 (Mi semr26)

This article is cited 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.

UDC: 517.920

MSC: 05E30

Received October 4, 2005, published November 3, 2005

Language: English



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024