✦ LIBER ✦

Embedding arbitrary finite simple graphs into small strongly regular graphs

✍ Scribed by Jajcay, Robert; Mesner, Dale

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 235 KB
Volume: 34
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(200005)34:1<1::aid-jgt1>3.0.co;2-e

No coin nor oath required. For personal study only.

✦ Synopsis

It is well known that any finite simple graph Γ is an induced subgraph of some exponentially larger strongly regular graph Γ (e.g., [2,8]). No general polynomial-size construction has been known. For a given finite simple graph Γ on v vertices, we present a construction of a strongly regular graph Γ on O(v 4 ) vertices that contains Γ as its induced subgraph. A discussion is included of the size of the smallest possible strongly regular graph with this property.