×

Embedding arbitrary finite simple graphs into small strongly regular graphs. (English) Zbl 0947.05089

Let \(f(v)\) denote the smallest positive integer for which every finite simple graph on \(v\) vertices can be embedded into some strongly regular graph on at most \(f(v)\) vertices. Van H. Vu [Combinatorica 16, No. 2, 295-299 (1996; Zbl 0858.05100)] constructed the family of strongly regular graphs based on Steiner triple systems, which gives the lower bound \(f(v)\geq c'\cdot v^2\). This paper gives the construction of strongly regular graphs based on Desarguesian affine planes, such that \(f(v)\leq c\cdot v^4\). It is proved that this upper bound is exact in a class of strongly regular graphs, obtained by this construction.

MSC:

05E30 Association schemes, strongly regular graphs
05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 0858.05100
Full Text: DOI

References:

[1] Babai, Euro J Combin 6 pp 101– (1985) · Zbl 0573.05032 · doi:10.1016/S0195-6698(85)80001-9
[2] Blass, J Graph Theory 5 pp 435– (1981) · Zbl 0472.05058 · doi:10.1002/jgt.3190050414
[3] and Graphs, codes and designs, London Math Soc Lecture Note Ser 43, Cambridge Univ Press.
[4] Erd?s, J London Math Soc 16 pp 212– (1941) · Zbl 0061.07301 · doi:10.1112/jlms/s1-16.4.212
[5] and A course in combinatorics, Cambridge Univ Press, 1992, pp. 231-249.
[6] Sidon, Math Ann 106 pp 539– (1932) · Zbl 0004.21203 · doi:10.1007/BF01455900
[7] Sidon, Acta Sci Math (Szeged) 7 pp 175– (1935)
[8] Vu, J Graph Theory 22 pp 137– (1996) · Zbl 0855.05050 · doi:10.1002/(SICI)1097-0118(199606)22:2<137::AID-JGT4>3.0.CO;2-O
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.