RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2005, том 2, страницы 218–221 (Mi semr26)

Эта публикация цитируется в 1 статье

Статьи

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

Аннотация: 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.

УДК: 517.920

MSC: 05E30

Поступила 4 октября 2005 г., опубликована 3 ноября 2005 г.

Язык публикации: английский



Реферативные базы данных:


© МИАН, 2024