Premium
Embedding arbitrary finite simple graphs into small strongly regular graphs
Author(s) -
Jajcay Robert,
Mesner Dale
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(200005)34:1<1::aid-jgt1>3.0.co;2-e
Subject(s) - combinatorics , mathematics , discrete mathematics , line graph , factor critical graph , symmetric graph , strongly regular graph , distance hereditary graph , block graph , regular graph , cograph , graph factorization , graph power , graph , voltage graph , pathwidth
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 υ vertices, we present a construction of a strongly regular graph Γ on O (υ 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. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 1–8, 2000