вход по аккаунту



код для вставкиСкачать
On the Embedding of
Graphs into Graphs with
Few Eigenvalues
Van H. Vu
NEW HAVEN, CT 0651 1
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.
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
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
= { ( 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)“;).
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
+ + €3
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
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.
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.
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
pN -
pN+l -
The proof can be finished by Proposition 1 and the existence of projective planes of
rank p.
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.
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
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.
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.
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:
a23 =
( t)
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:
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
to the plane
and ,Ll3;”1 be the correspondents of @ O ,
By a similar reasoning we have
p,”’, and p,”74in Sj+lwith respect
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
a, = 0,
+ 0,’3 1 +p,’3 4 + R;+, > a,+l3
= p3I0
,+I +p3”
+ ,i33’4 + R;+,,
which completes our proof.
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
l ) ( P + 1)
where q = (p”+l - 1) / ( p - 1). Since p and s can be chosen freely, we can suppose that
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:
First, note that
hence, ( 7 , ~ )= ( T , p
+ 1) = 1. The assertions will be proved undirectly.
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
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,
= 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.
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.
(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.
(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:
(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,
-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.
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.
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
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.
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.
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.
Case 1. X - p < 2n/3. In this case the above inequality implies that
+ 4(nl
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
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’.
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.
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.
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.
We would like to thank A. E. Brouwer and F. De Clerck for a number of useful comments
and advice.
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)
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. .
Theory Sel: A 18 (1975) 71-79.
Received February 21,1995
Без категории
Размер файла
726 Кб
Пожаловаться на содержимое документа