On the Embedding of Graphs into Graphs with Few Eigenvalues Van H. Vu DEPARTMENT OF MATHEMATICS YALE UNIVERSITY NEW HAVEN, CT 0651 1 E-MAIL: vuha@rnath.yale.edu ABSTRACT A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n,every graph can be embedded in n cospectral, non-isomorphic graphs of type k for every k 2 3. Furthermore, in the case k 2 5 such a family of extensions can be found at every sufficiently large order. Some bounds for the extension will also be given. 0 1996 John Wiley & Sons, inc. 1. INTRODUCTION A graph G(V,E) with the set of vertices V and the set of edges E is called simple if it has neither loops nor multiedges. In this paper we consider only simple graphs. An induced subgraph G’(V’,E’) of G(V,E) is a graph with V’ being a subset of V, and E’ consisting of all the edges between vertices of V’ in G. A graph G’ is called embeddable in G if it is isomorphic with some induced subgraph of G , we call G an extension of G’. The following notions and notations will be used in the rest of the paper. A S(2, q, v) Steiner system is a q-uniform hypergraph on v points such that every two points are contained in exactly one block (or edge). A partial design with block size q is a collection of blocks of size q such that every two points are contained in at most one block. More about designs can be found in the standard literature. A subsystem of a Steiner system is a set of some blocks of the system. The block graph of a partial design is a graph with blocks as vertices and two vertices being adjacent if the corresponding blocks have a common point. Journal of Graph Theory Vol. 22,No. 2, 137-1 49 (1 996) 0 1996 John Wiley & Sons, Inc. CCC 0364-9024/96/020137-I 3 138 JOURNAL OF GRAPH THEORY Let G1(Vl,El),Gz(V2,E,)be two arbitrary graphs with Vl n V2 = 0. The (disjoint) union of G1 and G2, denoted by G1 U Gz, is the graph with vertex set V = Vl u V2, and edge set E = El U Ez. We will denote by UiG the union of i, i > 1 graphs, each of which is isomorphic to G. The direct sum of GI and Ga denoted by G1 + Gz, is the graph obtained from the union of GI and G2 by joining every vertex of G1 to those of G2. We will denote by iG the direct sum of i graphs each of them being isomorphic to G. The complement of G(V, E ) is the graph G on the same set of vertices, two vertices in G being adjacent iff they are not adjacent in G. The product of G1 and G2 denoted by GlG2 is the graph with vertex set V = { (z,y)llz E Vl,y E V2) and ((z,y), (z’,y’)) E E if and only if ( z , ~ ’ E ) El and (y, y’) E E2. If z is an arbitrary vertex in a graph G(V, E ) , we denote by deg(z) the degree or valency of z. Furthermore, we introduce max deg(G) = max{deg(z)l/z E V } and mindeg(G) = min{deg(z)JJzE V}. The spectrum of a graph G is the family of eigenvalues of the (0, 1)-adjacency matrix of the graph. Since this matrix is symmetric, the spectrum of a graph on n vertices always consists of n real numbers, some of which can be equal; hence a graph on n vertices has at most n distinct values in its spectrum. Two graphs are called cospectral if their spectrum coincide. If G has 1 distinct eigenvalues E ~ . ., . ,E L with multiplicities respectively equal to m l , . . . , ml,then we will denote the spectrum of the graph G by Spec(G) = , . . . ,~ 7 Denote by K , the complete graph of order n.Clearly Spec(%) = { 0 7 L }while , Spec(K,) = { ( n - l)l,(-l)n-l}. Some connections between the spectrum of a graph and operations on that graph are described in the following theorem. Theorem 1. 1. The spectrum of the union of two graphs is the union of their spectra. 2. If G is a regular graph with valency n1 on n vertices, and PG(E)is the characteristic polynomial of the adjacency matrix of G, then if E is an eigenvalue of G different from the valency, then -E - 1 is an eigenvalue of G; n - n1 - 1 is an eigenvalue with multiplicity 1 of G. 3. If E is an eigenvalue of G and if E’ is an eigenvalue of G’, then EE’ is an eigenvalue of the product GG’. The first assertion is trivial; the second one was proved by H. Sachs (1962), by considering the generator function of the numbers of walks in G, (see [3], Theorem 2.6); the third one is a well-known fact in linear algebra, since the adjacency matrix of the product GIGz of GI and Gz is indeed the Kronecker product of the adjacency matrices of Gl and G2 [ 3 , 91. Corollary. The spectrum S p e c ( r z ) of the direct sum r z of r cocliques on n points equals { O ( T L - l ) T , (nr-n)l, (-n)‘-’}.The spectrum of the product K; of T complete graphs of order n consists of T -k 1 distinct eigenvalues E, = (-l)”(n - l)T-z, i = 0,1, . . . , T with respective multiplicities mz = (n- 1)“;). ~). EMBEDDING GRAPHS 139 Corollary. Let H = G1 U G2 U . . . U G,, n 2 2, be a graph on t vertices, where all Gi are regular graphs with valency 7x1. Assume Spec(H) = {&yl= nyl,E : ~ , . . . ,E ? } ; then by Theorem 1, Spec(I?) = { ( t- n1 - l)', (-€a - l ) m 2.,..,(-el - 1)"l, (-nl - 1)"1-1} and hence H is of type 1 1. + There are lots of classification theorems known for graphs with few distinct eigenvalues, (see, for instance, [3]). For example, all the graphs with one or two distinct eigenvalues have been classified by M. Doob [3, Theorem 6.41. Theorem 2. A graph G has only one eigenvalue if and only if G is a coclique it has two with multiplicities ml and m2 if and only if G is the disjoint distinct eigenvalues ~1 > union of ml complete graphs of order €1 + 1 each. At one time it was conjectured that cospectral graphs have to be isomorphic. It holds in fact in special cases (as in Theorem 2 for instance), but in general it is not true; lots of families of cospectral, nonisomorphic graphs have been found (see [3], chap. 6). Moreover, the following theorem shows that one can require that each member of the cospectral family has a given order and contains a given graph ([3], Theorem 6.2): Theorem 3. Let G be a given graph. Then for any integer n there is an N such that for every integer rn > N there exist n cospectral, nonisomorphic graphs, each of which has order m and contains G as an induced subgraph. Another family of graphs that have few distinct eigenvalues is the family of the strongly regular graphs, which have been introduced by R. C. Bose [l]. Definition. We call a noncomplete graph G(V, E ) strongly regular with parameters n l , A, p if and only if 1. The graph G is regular with valency n1. 2. For every 3:,y E V, (z, y) E E , z and y have exactly X common neighbors. 3. For every 5 , y E V,( 5 ,y) @ E , 3: and y have exactly p common neighbors. The following theorem is well-known (see for instance [3], Theorem 3.32). Theorem 4. A regular connected graph G of degree n1 is strongly regular with parameters nl, A, p iff it has exactly three distinct eigenvalues: E~ = 72.1, € 2 , and € 3 . Furthermore, = nl p = Or equivalently, E~ = 1/2[(X - p) + E2E3 + + €3 €2 721 + & 2 E 3 . * J(X - p)2 + 4(nl - p ) ] with i = 2 or 3. We will always assume that ~2 > c 3 . One can compute the multiplicities in function of the eigenvalues or the parameters. We consider the following notion, which is a generalization of the above graphs. Definition. A graph G is said to be of type k , k a positive integer, if it is connected, regular, and has exactly k distinct eigenvalues. For example, every distance regular graph of diameter k - 1 is of type k (for the definition of a distance regular graph, we refer to [2]). By Theorem 2 it is clear that a graph G 140 JOURNAL OF GRAPH THEORY is of type 1 iff it contains only one vertex, and is of type 2 iff it is a complete graph on at least two vertices. Theorem 4 deduces that a connected graph is strongly regular if and only if it is of type 3. It is also well known that if a regular graph is connected, then the largest eigenvalue is the valency and it has multiplicity 1. By the observations above, it is trivial that the set of all the induced subgraphs of graphs of type 1 or 2 is the set of complete graphs, which in fact forms a very small and special class of the set of all possible graphs. A natural question arises: What can we say about graphs of larger type? The following theorem gives us the answer, which can also be regarded as a restriction of Theorem 3 on families of graphs of given type. Main Result. Let n be an arbitrary positive integer and G an arbitrary graph. (a) For k = 3 or 4,there is a positive integer M ( n ,k ) such that there exists a family of n cospectral, nonisomorphic graphs of type k and order M ( n , k ) , each of which contains G as an induced subgraph. (b) For every k 2 5, there is a number N ( n ,k ) such that for every positive integer m > N ( n ,k ) there exists a family of n cospectral, nonisomorphic graphs of type k and order m, each of which contains G as an induced subgraph. The well-known strongly regular graphs are usually characterized by the parameters. For this reason the case k = 3 is quite interesting, where we construct a large family of nonisomorphic strongly regular graphs of the same parameters. This is also the basic step of the proof. 2. PROOF OF THE MAIN RESULT The proof of the main result is based on some theorems on embedding partial designs into Steiner systems. First we mention some of the most important results and techniques in this area. + Proposition 1. Let S be a S ( 2 ,q , w) Steiner system. If there exists a S(2,q, q2 - q 1) Steiner system, then there exists a S(2,q, v(q - 1) 1) Steiner system that contains S as a subsystem. + Proposition 2. Suppose that S is a S(2,q,w) Steiner system and that there exists a S(2,k , q ) Steiner system; then by defining on every block of S a S(2,k , q ) Steiner system, the resulting system is a S ( 2 ,k , v ) Steiner system. Proposition 3. Let S be a S(2,q,w) Steiner system with R being a subset of the set of points of S. Assume that a subsystem PI formed by the blocks on R is a Steiner system and P2 is another Steiner system on R; then by replacing PI by Pz we obtain a new S(2,q , w) Steiner system. Proposition 4. The block graph of a S(2,q , u)Steiner system is a strongly regular graph with parameters nl = (v - q ) q / ( q- l),X = ( q - l)z (w - 2q l ) / ( q - 1) and p = q2. + + The construction that proves Proposition 1 can be seen in [7]; the other three are trivial. EMBEDDING GRAPHS 141 Theorem 5 (Ganter [4]). Every partial design with block size ( p + 1) can be embedded in a Steiner system with the same block size if p is a prime number. Corollary. Let p be a prime and H be a partial design with block size p + 1; then there is a constant N such that for every positive integer y 2 N , H can be embedded in a S ( 2 , p + 1,(p? - l)/(p - 1))Steiner system. Proof. One can easily show that the extension of H constructed in the proof by Ganter of theorem 1 has ( p N - l ) / ( p - 1) points for some N (see [4]). Note that 1 p-lP+l= pN - pN+l - P-1 1 . The proof can be finished by Proposition 1 and the existence of projective planes of rank p. I Using the result of Theorem 5, Quackenbush (see [ 101) proved the following: Theorem 6. Every partial design with block size p" can be embedded in a Steiner system if p is a prime number. Combining the techniques used by Quackenbush and the result of Corollary 3 we can easily prove a similar result for partial designs with block size p. Corollary. Let p be a prime number and H a partial design with block size p ; then there is a constant N such that for every positive integer y 2 N , H can be embedded in a S ( 2 , p , p 7 ) Steiner system. It is clear that if Steiner systems with parameters q and v exist, then q and v must satisfy Q - IlV - 1 and q(q - l)lv(v - 1) In 1975 Wilson (see [l 11) proved that these necessary conditions are also sufficient for sufficiently large w. By Wilson's theorem, the following corollary is trivial: Corollary. Let q be an arbitrary positive integer; then there is a constant N such that for every positive integer T 2 N one can find a Steiner system of parameters q and W = q(q - 1)' + 1. Using Wilson's theorem, Ganter in [ 5 ] proved the generalization of Theorem 5. Theorem 7. A partial design can always be embedded in a Steiner system. The mentioned results will be used to prove the theorems that now follow and will be crucial in the proof of the main result. Theorem 8. Let q be a positive integer and H an arbitrary partial design with block size q. There exists a positive integer T satisfying (q(q - l ) , ~=)1 such that H can be embedded in a Steiner system on v = T q ( q - 1)+ 1 points. 142 JOURNAL OF GRAPH THEORY Proof. By Corollary 5 and Dirichlet's theorem there is a positive integer + + < such that qo = q 2 ( q - 1)'< q(q - 1) 1 is a prime number and a S(2,q , qo) Steiner system exists. Denote F1 = q(q - l)< 1; it is obvious that qo = q ( g - l)tl 1 and ( q ( q- l),tl)= 1. Let b l , b2,. . . ,b,, be the blocks of H . Let X I ,X Z ,. . . , X , be n pairwise disjoint sets, each of which is disjoint from H and IX, I = qo - q . Denote B, = b, U X , and H' the partial design with block size qo formed by the B,(i = 1 , 2 , . . . , n). By Corollary 4 there is a positive integer y, (7, q ( q - 1))= 1 such that H' can be embedded in a S(2,qo,qOy) Steiner system. On every block of this Steiner system we define a S(2, q, qo) Steiner system such that all the b, are blocks; this is clearly possible. The resulting system is a S ( 2 , q , q;) Steiner + + system by Proposition 2 and contains H as a subsystem by the condition. To complete the proof, we show that w = q: has the required property. Consider Let Clearly w = qOy = T q ( q - 1)+ 1. On the other hand, (q(q - l),7) = ( q ( q - 1 ) , y t l ) = 1 by the way we have chosen y and El, and this completes the proof. I Theorem 9. Let n be a positive integer. Every partial design with block size p + 1,p a prime, can be embedded into n different Steiner systems with the same parameters, every pair of which have nonisomorphic block graphs. Proof. Let s be an arbitrary positive integer larger. Then 2 and q = ( p " + l - l)/(p - 1). Let H be the given partial design with blocks bl,b2,. . . , b,. Let X1,X 2 , . . . , X , and B1,B 2 , .. . ,B, be pairwise disjoint sets, each of which is disjoint from H . Furthermore, lXil = q - p - 1 and lBjl = q. Denote Ai = XiU bi for i = 1 , 2 , . . . , m and H' the partial design with block size q consisting of Ai(i = 0 , 1 , 2 , . . . , m) and B j ( j = 1 , 2 , . . . , n). By Theorem 7 we can extend H' to a Steiner system S on 21 points. On every block B of S except B1, BS,. . . , B, construct a projective space of dimension s over G F ( p ) with an extra condition that if bi c B,then bi is a line in this space. In each B j ,j = 1 , 2 , . . . , n fix a set R j of p2 + p + 1 points. On the points of R j define two projective planes Pi and P; such that there are two lines 2: and 1; contained in Pi and P: respectively satisfying p + 1 > 12; n 131 > 1. We say four lines form a complete quadrangle if every pair of them share a point in common and no three go through the same point. The lines are called edges of the complete quadrangle. For each Pj, i = 1 , 2 , and j = 1 , 2 , . . . , n, denote by Rj the number of complete quadrangles in the resulting system that have exactly one edge as a line in Pi. Note that none of the edges of these complete quadrangles is contained in BI, if k # j because B k and Bj are disjoint. Without loss of generality we can assume that R: 2 R; for every j = 1 , 2 , . . . ,n. EMBEDDING GRAPHS 143 We construct in each B, a projective space of dimension s such that P; is a subspace of this space. Denote by So the set of lines in all the spaces constructed on the blocks of S. By Proposition 2 it is clear that SO is a Steiner system. For j = 1 , 2 , . . . ,n call S, the system of lines obtained from SOby replacing the lines of Pi by those of Pt for every k 5 3 . Since the B3 are disjoint from H, all the resulting systems still contain H as a subsystem; moreover, they are S ( 2 , p + 1,u) Steiner systems by Proposition 3. To complete the proof we claim that the block graphs of the S, are nonisomorphic. Let N, be the number of K4 contained in the block graph of S, as a subgraph; it is sufficient to prove that N, > N,+1 of every j = 0 , 1 , 2 , . . . , n - 1. Note that if the subgraph spanned by four points A, B , C, D of the block graph of a Steiner system is K4, Then the corresponding four lines a, b, c, d in the system must satisfy one of the following conditions: 1. They are concurrent. 2. Three of them are concurrent and the fourth intersects all of the others. 3. They are edges of a complete quadrangle. Let a;, a;, a; be the number of quadruples of lines in S, satisfying the first, second, and third condition, respectively. It is trivial that One can easily show that the numbers a; and a: depend on the parameters of the system only, in fact: = u(;), a23 = ( t) a31. p 2 ( p - 1)/3, where d = (w - l)/p denotes the number of lines going through a fixed point in Sj(j = 0,1,2, . . . , n). We are going to prove that a: > a;+1.First of all, note that the difference between Sj and Sj+l occurs only in the set of lines on Rj+l. On the other hand, observe that the situation of the edges of a complete quadrangle in Sj should be one of the following four types: 1. 2. 3. 4. None of these lines is contained in Bj+l. All of them are contained in Bj+l. Exactly one line is contained in Bj+lbut not in Pj+l. Exactly one line lies on Pj+l and none of the other three is contained in Bj+l. Denote by pi7”@4, and Pi1’, respectively, the numbers of complete quadrangles in Sj of the first, second, and third type. The number of complete quadrangles of the fourth type is Rj+l by its definition. Since the types do not overlap, we have Let /3:$1, to the plane and ,Ll3;”1 be the correspondents of @ O , By a similar reasoning we have p,”’, and p,”74in Sj+lwith respect 144 JOURNAL OF GRAPH THEORY By the construction of the S, it is clear that Note that in both S, and S,+, the lines in BJfl form a S ( 2 , p + 1, q ) Steiner system. fix a point .7: and two We count /3f)4in the following way. Consider the system 5,; in lines ZI, Z2 through 2 . First we count the number of complete quadrangles in B,+lhaving these lines as edges. Let 13 and l4 be two other lines contained in B,+, each of which intersects 11 and 12 but does not go through z. Since in S, the lines of B,+l are those of a projective plane, the two lines 13 and 14 must intersect each other by the Veblen-Young axiom. Hence, 11,12, Z3, and 14 form a complete quadrangle and there are p 2 ( p - l)”2 complete quadrangles in B,+1 with l1 and l2 as edges. Thus We make the same calculation in S,+I. Note that the existence of the pair (li+I,l;+l) implies that in S,+, the Pasch axiom fails in some cases, i.e., there are a point .7: and four lines 1 1 , 1 2 , 1 3 , 1 4 in B,+, satisfying the above conditions, but 13n14= 0. Hence > p;$l. Combining this with the assumption R:+l 2 R:+l we obtain that 3 3,O a, = 0, + 0,’3 1 +p,’3 4 + R;+, > a,+l3 = p3I0 ,+I +p3” 3+1 + ,i33’4 + R;+,, 3fl which completes our proof. I Remark. If two Steiner systems have nonisomorphic block graphs, then they are nonisomorphic. The converse statement is not true; for instance, two nonisomorphic projective planes of order n have the same block graph Kn2+n+l. Let Gs, be the block graph of S j ; their order and valency are, respectively, t = -v(v - 1) p ( p + 1) and .( = - P l ) ( P + 1) , P - where q = (p”+l - 1) / ( p - 1). Since p and s can be chosen freely, we can suppose that p l(3) and let s = 5. By Theorem 8 we can assume that v = q(q - 1)‘ 1 and (q(q - l), T) = 1. To prove the main result, we need the following lemma: -- + Lemma 1. Under the above assumptions, the following holds: Proof. First, note that hence, ( 7 , ~ )= ( T , p + 1) = 1. The assertions will be proved undirectly. EMBEDDING GRAPHS 145 + a. Assume that (nl 1,t) # 1. Then there exists a prime number po that is a common divisor of n1 1 and t. Thus polt(p 1)2- v(nl 1) = vp. Two cases are to be considered: + + + 1. po = p. Note that nl + 1 = ((v - l)(p+ l))/p - p , so plnl By the above assumptions we have + 1 iff pl(v - l)/p. which is evidently not divisible by p since (p,T) = 1, a contradiction. 2. polv. Observe that polp(n1 1) = v ( p 1) - (p2 + p 1); hence polp2 + p On the other hand, + 21 = Q(Q - + 1). -k 1 = (p5 + + 1. + p4 + . . . + p + l)(Q- 1)'T = (p2+p+i)(p3+1)(q-i)T+1; thus ( v , p 2 + p + 1) = 1, a contradiction. b. Similarly, assume that there is a prime number po that is a common divisor of t and 2nl. By an easy counting one can show that which is odd; hence po # 2 and is the common divisor of nl and t. Thus po is a divisor of t(p 1)2- n1w = v ( p + 1). Note that if polv, then by the observation that polnlp = v ( p 1) - (p 1)2 one can show that polp + 1. So, we can always assume that polp 1. On the other hand, by a simple counting and the assumption that p = 1(3),we can see that + + + ( v , p + 1) = ( p 4 + p 2 + + i , p +1) = (p4+p3 + p 2 + p + I , ~ 1) + = 1. Moreover, note that ( ~ , p 1) + = 1. The above expression o f t implies that ( t , p + 1) = 1, a contradiction and our proof is complete. I Proof of the Main Result. Consider the graph G(V,E), let HG be the dual hypergraph of G, i.e., the hypergraph the incidence matrix of which is the transposed of that of G. Let b l , b 2 , . . . , blvl be the blocks of HG and p a prime satisfying the lemma and p 2 max Ibil. Let XI, X 2 , . . . ,Xlvl be pairwise disjoint sets, each of which is disjoint from HG and lXil = p + 1 - Ibil. Denote Bi = bi u Xiand H the hypergraph formed by the Bi. It is obvious that H is a partial design with block size p + 1since G is a simple graph; moreover, the block graph of H is isomorphic to G by its construction. (a.1) k = 3. Let S1,S2, .. . ,S, be the Steiner systems constructed in Theorem 9, each of which contains H as a subsystem. It was proved that the block graphs of the Si are nonisomorphic; on the other hand, they are all strongly regular graphs with the same parameters since the Sihave the same parameters. Hence, they are cospectral by Theorem 4. The duality guarantees that each of these graphs contains G as an induced subgraph and this completes our proof in this case. 146 JOURNAL OF GRAPH THEORY (a.2) k = 4. By (a.1) the graph G can be embedded in n cospectral, nonisomorregular graphs GI,G2,. . . ,G, with Spec(Gi) = { n l , ~3""). The graphs U2G1, U2G2, . . . , U2G, are of type 4 by Corollary 2 of Theorem 1 and contain G as an induced subgraph. Furthermore, they are cospectral and nonisomorphic by the construction and this ends the proof of this case. &T2, phic _ _strongly __ (b.1) k = 5 . Consider the graphs Gi, i = 1 , 2 , . . . , n mentioned in (a.2). By the lemma we can assume that the common order t and valency nl of the Gi satisfy that ( t ,n1 + 1) = 1. Let N = t(nl I ) , observe that for every m > N we can find two positive integers u and w such that m = ut + w(n1 + I) since ( t ,n1 + 1) = 1. Consider the following graphs: + Gi = (UZLGZ) U (UwKnl+l),i= 1 , 2 , . . . ,n. By the observation above, the G: have common order m and valency nl.On the other hand, by Theorem 1 they have 4 distinct eigenvalues and -1. Corollary 2 of Theorem 1 implies that the graphs are of type 5. Moreover, by their construction these graphs contain G as an induced subgraph. They are cospectral and nonisomorphic by the same reason. (b.2) k 2 6. The proof uses the similar method as in (b.l)> Consider again the graphs GI, G2,.. . , G, mentioned in (a.2) that are extensions of G. By the lemma we can assume that their common orders t and valencies n1 satisfy that ( t ,2nl) = 1.Moreover, choose the prime p at the beginning of the proof such that p 1 has at least k - 4 nontrivial divisors p l , p z , . . . ,pkP4;this is clearly possible.' Since p llnl it follows that n l / p l are integers. Without loss of generality we can suppose that none of nl/pl(Z = 1,2, . . . , k - 6) is equal to E~ or c3. Consider the following graph: + + by Theorem 1 it is obvious that G* has k - 4 distinct eigenvalues: n1,0, - n l / p l ( l = 1 , 2 , . . . , k - 6). Let N = 2nlt v* where v* denotes the order of G*. Since (2nl,t ) = 1, every positive integer m > N can be written in the form: m = ut + 2wnl + v* where u and w are positive integers. Consider the following graphs: + ~ GI = (U,Gi) U (Uw2Kn,) U G*,i = 1,2,.. . ,n. By the construction and Theorem 1 the regular graphs G: are of order m and have valency n l . Moreover, they are cospectral and have k - 1 distinct eigenvalues n l , E Z , ~ 3 , 0-nl, , and -nl/pl(Z = 1,2, . . . , Ic - 6). Hence by Corollary 2 of Theorem 1 each of the is of type k . By the construction and Theorem 1 they are cospectral and nonisomorphic, and each of them contains G as an induced subgraph. Thus the theorem is proved. I 3. BOUNDS FOR THE EMBEDDING IN STRONGLY REGULAR GRAPHS In the proof of the main result, the embedding of the graph G in a strongly regular graph plays an important role. Hence we want to consider this case in more detail. EMBEDDING GRAPHS 147 So, in the following we try to give some bounds for the extension of a graph to a strongly regular graph. The main tool that we are using here is the following theorem, known as Cauchy's inequality or the interlacing law (see for instance [9], p. 119). Theorem 10. Let A be a Hermitian matrix with eigenvalues c1 2 E~ 2 . . . 2 E,,B be 5 one of its principal submatrices having eigenvalues p1 2 p2 2 ... 2 p m ; then E,-,+~ pi I ~i with 1 5 a 5 m. Obviously the theorem holds for every adjacency matrix A of a graph and for B the adjacency matrix of an induced subgraph of this graph. By this observation, the following lower bound follows immediately. Theorem 11. For every n there is a graph of order n, which cannot be embedded in a strongly regular graph on less than en2 vertices for some positive constant c. Proof. Consider the graph G = K,+l u 2 z ; then Spec(G) = {n2,-nl, -1,, 02"-2}. Let G' be a strongly regular graph that contains G as an induced subgraph. By Theorem 10, the eigenvalues > E~ of G' satisfy If p > A, then the first inequality yields: which proves our claim. If X 2 p, we can use the second inequality to prove the claim. I Remark. Following the proof of the main result, one can easily see that the size of a strongly regular extension of a graph depends on the size of the Steiner extension of partial design obtained from the dual hypergraph of the give graph. Unfortunately, the size of the Steiner extensions of partial designs is awfully large, since they are constructed by induction. The only exception being the case of block size 3. Indeed, by another method C. C. Lindner proved that every partial design with block size 3 on t points can be embedded in a Steiner triple system of less than 6t 3 points [6]. This result has been improved to 4t 4 by Hilton, Mendelsohn, and Andersen [7]. Now, let G be a graph of order n that can be regarded as a block graph of a partial design with block size 3 (for example, every line graph is of this kind). Clearly this design cannot have more than 3n points, and by the results above it can be embedded in a Steiner system on no more than 12n 4 points; hence, the block graph of this system, which is strongly regular, has no more than (12n + 4)(12n + 3)/6 = 24n2 vertices and has p = 32 = 9. So, we have deduced the following theorem. + + + 148 JOURNAL OF GRAPH THEORY Theorem 12. Every graph that can be seen as a block graph of a triple partial design can be embedded in a strongly regular graph of order less than cn’ with p = 9, where c is an absolute constant. The next theorem shows that in this case n’ is the best possible bound one can expect. Theorem 13. There is a positive constant c’ such that for every n; there is a line graph of order n, which cannot be embedded in a strongly regular graph with p = 9, containing less than c’n’ vertices. Proof. Consider the graph G = K,,, U U K,,, , which is obviously a line graph. By Theorem 1, Spec(G) = (n’, On+’, -1’”); hence the second largest eigenvalue of G is n. Let G’ be a strongly regular graph on n’ vertices with parameters n l , A, and p = 9, which is an extension of G. By Cauchy’s inequality the eigenvalue E:! of G’ satisfies E~ 2 n. Hence Case 1. X - p < 2n/3. In this case the above inequality implies that J(X - p)’ + 4(nl - p) 2 2n - (A - p ) > 4/31 + (A - p)’ + 4(nl - p ) > 16/9n2 But -9 5 X - p 5 2/3n; therefore for n > 14, (A - p)’ < 4/9n2. Hence 4(nl - p ) > 16/9n2 - (A - p)’ > 12/9n2 and so n’ > n1 > n l - p > 1/3n2. Case 2. X - p 2 2n/3. Consider the matrix A’, the matrix A being the adjacency matrix of G’. The trace of A’ is the sum of the squares of the eigenvalues of A, namely n ~ + r n 2 ~ ~ +On mthe 3 ~other ~ . hand, it is indeed the sum of the degrees of all vertices of GI, m& = 71’721. It follows that n’n1 > r n 2 ~ ; . and thus equals n’nl. So we have nf + rn& Note that G has n + 3 non-negative eigenvalues, so G’ should have at least that many non-negative eigenvalues because of the Cauchy inequality, which means that r n 2 2 n + 2. Furthermore, E Z 2 X - p 2 2/3n, hence + If n1 - X 5 n + 1, then 5 in’ = 2n’. 9 for every n > 30. Thus n’ > . If n1- X > n+ 1,by the following well-known equality between parameters in strongly regular graphs: (n’ - n1- 1)p = n1(nl - X - l),and because p = 9, it follows immediately that n1 > X+n > 5/3n andn’ > (1/9).(5/3)n2+(5/3)n+l > (5n2/27), whichcompletes our proof (just observe that it does not matter that G has 372 + 3 vertices). The constant c’ can easily be determined by some careful counting. I Remark. Results in [8] imply that every graph of order n with Ic = max{max deg(G),nmin deg(G)} can be embedded in the graph of type lc + 1 of order roughly nk. EMBEDDING GRAPHS 149 4. OPEN PROBLEM As we have mentioned in the introduction, every distance regular graph with diameter k - 1 is of type k. One can wonder whether it is true that every graph can be embedded in a distance regular graph with diameter k 2 3. For example, it is easy to prove that every bipartite graph can be embedded in a Hadamard graph ([2] p. 20) which is distance regular of diameter 4 by extending (1,-1) matrices to Hadarnard matrices. However, the answer in the general case is not known. ACKNOWLEDGMENTS We would like to thank A. E. Brouwer and F. De Clerck for a number of useful comments and advice. References R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs. Pac. J. Math. 13 (1963) 389-419. A. E. Brouwer, A. M. Cohen, and A. Neumaier. Distance-Regular Graphs. Springer Verlag, Berlin (1989). D. M. CvetkoviC, M. Doob, and H. Sachs, Spectra of Graphs. Academic Press, New York ( 1980). B. Ganter, Endliche Vervollsthdigung endlicher partieller Stenerscher Systeme. Arch. Math. 22 (1971) 328-332. B. Ganter, Partial pairwise balanced designs. Coll. Intemz. Teorie Combinat. (Roma) 2 (1973) 377-380. C. C. Lindner, A partial Steiner triple system of order n can be embedded in a Steiner triple system of order 6n + 3. J. Combinat. Theory Sex A 18 (1975) 349-351. C. C. Lindner, Embedding theorem for Steiner systems. Ann. Discrete Math. 7 (1980) 175-202. L. Lovasz, J. NeSetiil, and A. Pultr, On a product dimension of graphs. J. Combinat. Theory Sex B 29 (1980) 47-67. M. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon, Boston (1964). R. W. Quackenbush, Near vector spaces over GF(q) and (v,Q + 1,1)-BIBDS. Linear Alg. AppZ. 10 (1975) 259-266. R. M. Wilson, An existence theory for pairwise balanced designs, I11 Proof of the existence conjecture. . I Combinat. . Theory Sel: A 18 (1975) 71-79. Received February 21,1995

1/--страниц