close

Вход

Забыли?

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

?

205

код для вставкиСкачать
On Generalized Cages
Cong Fan
DEPARTMENT OF MATHEMATICS AND STATISTICS
WESTERN MICHIGAN UNIVERSITY
KALAMAZOO, MICHIGAN 49008
ABSTRACT
In this paper, we give a generalization to the well-known cage concept as follows: We
define an (r,g, k)-cage to be an r ( k - 1)-regular graph of minimum order in which every
clique has k vertices, every vertex is in r cliques, and the minimum length of a cycle
with edges from distinct cliques is g. Clearly, when g 2 4 and k = 2, an ( r ,g, 2)-cage is
just a usual ( r ,g)-cage. Here we prove that an ( r ,g, k)-cage always exists for g 2 4. We
examine the lower bounds for the order of (r,g, k)-cages and also explore some connections of these generalized cages with generalized polygons, strongly regular graphs, and
Moore geometries, which give rise to certain ( r ,g, k)-cages. 0 1996 John Wiley & Sons, Inc.
1. INTRODUCTION
For r 2 2 and g 2 3, an (r,g)-cage is an r-regular graph of minimum order f ( r ,g) which
has girth g. That an ( r ,g)-cage always exists has been proved by Erdos and Sachs [4].For
a good survey on cages, see Wong 191.
A clique of a graph G is a maximal complete subgraph of G. Note that in an r-regular
graph with girth g 2 4,every clique is a K 2 , each vertex is in r cliques, and the girth g is
the same as the minimum length of a cycle with edges from distinct cliques. An (r,g)-cage
is simply such a graph of minimum order. This observation leads us to give the following
generalization of the cage concept.
Definition. For k 2 2, r 2 2, and g 2 4,let f ( r ,g, 5 ) be the smallest positive integer for
which there exists an r ( k - 1)-regular graph with f ( r ,g, k) vertices such that every clique
has k vertices, every vertex is in r cliques, and the minimum length of a cycle with edges
from distinct cliques is g. We define such a graph of order f ( r ,g, k ) to be an ( r ,g, k)-cage.
For example, it is easy to see that the line graph L ( P ) of the Petersen graph P is a (2,
5, 3)-cage. (See Figure 1.)
Journal of Graph Theory Vol. 23, No. 1, 21-31 (1996)
0 1996 John Wiley & Sons, Inc.
CCC 0364-9024/96/010021-11
22 JOURNAL OF GRAPH THEORY
FIGURE 1. The line graph of the Petersen graph
An r-regular graph G of order n is said to be [n,r, A, p]-strongly regular if every two
adjacent vertices of G have X common neighbors and every two non-adjacent vertices have
p common neighbors. For more information about strongly regular graphs, see [2]. For
convenience, we call an r-regular graph of n vertices [n,r, XI-semi-strongly regular if every
two adjacent vertices of G have X common neighbors.
We say that a graph G is clique-disjoint if every pair of distinct cliques of G are edgedisjoint. Clearly, if an [n,r, A]-semi-strongly regular graph G is clique-disjoint, then every
clique in G has exactly X + 2 vertices. Given a clique-disjoint graph G, define the
geometric-girth of G to be the minimum length of a cycle in G with edges from distinct
cliques. By the definition, it is easy to see that an ( r ,g, k)-cage is a minimum possible
clique-disjoint [n,r ( k - l),k - 21-semi-strongly regular graph with geometric-girth g.
In Section 2, we prove that for g 2 4, an ( r ,g , k)-cage always exists. Then, in Section 3,
we examine the lower bounds for the number f ( r ,g, k ) and show some connections of generalized cages with generalized polygons, strongly regular graphs, and Moore geometries.
Certain ( r ,g , k)-cages are obtained from the existing generalized polygons.
By convention, certain letters have a consistant meaning throughout the paper, as for
instance, in a clique-disjoint [TZ, r ( k - l),/\]-semi-strongly regular graph, A will always
stand for the number of common neighbors between two adjacent vertices, k for the
number of vertices in a clique, T for the number of cliques on a vertex, and g for the
geometric-girth.
2. EXISTENCE OF GENERALIZED CAGES
Lemma 1. For g 2 5, if there exists an ( r ,g, k)-cage of order f ( r ,g, k ) , then there also
exists an ( r , g - 1,k)-cage of order f ( r ,g - 1, k ) , and f ( r ,g - 1,k ) 5 f ( r ,9, k ) .
Proof. For k = 2, f ( r ,g, 2) is the same as f ( r ,g), the order of an ( r ,g)-cage. It is known
that f ( r , g - 1) <_ f ( r , g ) (see [9]). Thus, we assume k >_ 3. Let G be an (r,g,k)-cage and
let C = u1u2. . . u,Iul be a cycle of length g in G such that edge U , U , + ~ is in clique F, for
1 5 z 5 g, where aqfl= u1 and F, f F7 for i # j . Let V ( F 1 )= (u1,u2,vl,
v2,.. . , u k - - 2 }
and V ( F 2 ) = { u ~ ,UuJ ~
~ ,,
U I. .~ ., , wkp2}.
Suppose that G* is the graph obtained from G
ON GENERALIZED CAGES 23
by replacing two cliques FI and Fl with two new cliques F; and Fl on the vertex sets
(V(I.;)- {ul}) U {wl} and (V(F2)- {wl}) U { u l ) respectively. Then it is clear that G' is a
. . uguI
clique-disjoint graph with every vertex in r cliques which has a cycle C' = u1u32l~
with edges from different cliques. Thus the geometric-girth of G* is at most g - 1. We
now claim that the geometric-girth of G* is g - 1. Suppose, to the contrary, that G* has a
cycle C* = 0 1 0 2 . . aha1 of length 4 5 h 5 g - 2 with edges from distinct cliques. Then
C' has at least h - 2 edges from distinct cliques of G other than FI and F2 and at least one
newedge,i.e.,anedgeinEl={u1uz,ulwJ12<j 5 k - 2 ) o r E 2 = { w l v , J 1 <-j i k - 2 } .
Since El is contained in the clique I?. and E? is contained in the clique Pi, C* contains at
most one edge from each E,. If C' contains exactly one new edge a1u2 in El u E 2 , then
u2 # a1 and u2. It follows that G has a cycle a l u z a 2 a 3 . . . aha1 of length h + 1 5 g - 1
with at least h edges from distinct cliques, which implies that the geometric-girth of G is
at most g - 1, a contradiction. If C* contains two new edges, say a1a2 = u l a 2 , where
a2 = u3 or w,, and a3aJ+1= wlv,, for some j between 3 and h - 1, then the other edges
of C" are from distinct cliques of G other than Fl and F2. In this case, G has a cycle
a2a3 . . . a l a 2 for w1 = a3 or a cycle a2aJ+1a,+2 ...ahala,aJ-la,-2
" ' a 2 for w1 = u7+1
of length at most h 5 g - 2 whose edges are from distinct cliques, again a contradiction.
Thus, there exists an (r,g - 1,k)-cage and f ( r ,g - 1,k ) 5 f ( r ,g . k ) .
I
We define the distance d ( H 1 ,H2) between two subgraphs of a graph G to be the shortest
distance from any vertex v1 E H1 to any vertex v2 E H2. For convenience, we shall invent
names for certain quantities that arise repeatedly, specifically let
' p ( r , g , k )= 1
+ (r - l)(k
-
1)
+ (r
-
1)2(k
-
1)2
+ " . + ( r - 1)g-2(k
-
1)g-2
and
h(r,g,k ) = k ( k - l)[p(r,g,k ) + ( r - 1)"2(k
-
l)g-l]
+ 1.
For each vertex 'u of a graph G, let c (u) be the number of cliques in G which contain
Suppose that G = (V, E) is a clique-disjoint graph with Ic vertices in each clique such
that r - 1 5 c(z) 5 T for all z E V. Then we have the following immediate inequalities:
(1) If p E V and c ( p ) = r - 1, then
'u.
I{.
(2) Let
Kk
E VId(z,P) i 9
-
2)l
5 'p(r,g,k)
be a clique in G. Then
I{.
E V14zc,Kk.1 I
9 - 211
i kcp(r,9 , k ) .
Let G(T,g, k ) = {GIG is a clique-disjoint [n,r ( k - l),A]-semi-strongly regular graph
with A = k - 2, c(z) = T for all J: E V ( G )and geometric-girth at least 9).
These quantities happen to lead to the proof of Theorem 1, but the reason they have
been chosen will not be evident until we reach the end of the proof. And the proof is
motivated by a method in [8].
Theorem 1. For k 2 2, g 2 4, T 2 1, n 2 h ( r , g , k ) and n
graph G E G(r,g,k) so that IV(G)l = n.
= 0 (mod k ) , there exists a
Proof (by induction on r). The theorem obviously holds for r = 1. Assume the result
is true for r - 1, where T > 1. Since n 2 h(r,g, k ) > h(r - 1,g, k ) , there exists a graph
24 JOURNAL OF GRAPH THEORY
Go E G(T- 1,g, k ) of order n. Let
N
=
{ H I H is a clique-disjoint graph of order n with k vertices in each clique,
r - 1 I C ( X ) I T for any z E V ( H ) ,and geometric-girth at least 9).
Then N # 0 since Go E N. Let c(G)be the number of cliques in graph G. Assume G E N
such that c(G) 2 c ( H ) for every H E N. We claim that G is the desired graph (i.e.,
G E G(r,g, k ) ) .
To prove the claim, it suffices to show that c(z) = r, for every z E V ( G ) .Suppose,
) r - 1) # 0. The number of distinct pairs
to the contrary, that V’ = {X(X E V ( G ) , c ( z =
( ~ , K I with
; ) z in KI;is kc(G) = nr - IV’I. Since n = 0 (mod k ) , IV’I is a multiple of k
and so IV’I 2 k . Let A be a subset of V’ and IAl = k. Next we will show that G has k - 1
distinct cliques Q1,Q 2 ,. . . , Q I ; - ~such that
(1)
d(Q,,A)?g-l
and
Suppose that G has at most m cliques &I, Qz,. . . ,Qm satisfying (1) and (2) and 0 5 m 5
k - 2. Let
and let
C
= {X E
V ( G ) J d (B
z ,) 5 g - 2).
Then
ICI I
( m+ l)kCp(r,g, k ) I k(k - l)Cp(r,g, k).
Define D = V ( G )- C ; then
ID1 = n - ICI > k(k - 1)(.
-
1)g-yk
-
1)g-1
The set D contains no KI;by the maximality condition on m. Let
E = {U
Then [El 5 (m + l ) k ( r - l)g-’(k
D’
E
-
=
V(G)ld(v,B)= g
-
1)g-2 5 k ( r - l)”’(k
{ K I ; I V ( Kn
~ )D
a}.
-
1)g-l. Let
# 0).
Since D contains no clique KI; and the vertices of D are at distance at least g - 1 from
B , it follows that if Kk E D’,then KI;n E # 8 and ~ ( K I C; )E U D. Since each vertex in
E is in at most T - 1 cliques Kk in D’, it follows that
ON GENERALIZED CAGES 25
Also since each vertex of D is in at least r - 1 cliques Kk in D’ and every KI, in D’
contains at most k - 1 vertices in D , we have
We now have the contradiction
k(k
-
1)(r - l)”-”(k
-
1)g-l
< ID1
k-1
r-1
5 -1D’I
5 ( k - 1)IEl 5 k(k - 1)(r - 1)gP2(k - 1 ) g - l .
Thus, G has Q1,Q2 ,..., Q I , - ~satisfying (1) and (2). Since A,V(Q1),V(Q2)
,...,
V(Qk-1) are k disjoint sets each with k elements, there are disjoint sets X1,X2,.. . , X I ,
such that JX,I= k and
IX, n A1
=
1, IX,nV(Q3)I = 1 for 1 5 i 5 k , l 5 j 5 k - 1.
Now, let GI = G - (E(Q1) U E(Q2)U . . . u E(QkPl)) and Gz be the graph obtained
from G1 by joining all possible pairs of vertices in each X,and denote the new cliques
on each X, by 2,. Clearly, GZ is a clique-disjoint graph with k vertices in every clique
and C ( X ) = r - 1 or T for all 5 E V(G2). We now show that G2 has geometric-girth at
least g. Suppose, to the contrary, that G2 contains a cycle e1e2 . . . ebel with length b < g
such that each edge e, is from a different clique F,. Since the geometric-girth of G is
at least g, one of the cliques F3 must be one of the Z,, say Fl = Z1. Let p E Fl n F 2
and q E F1 n Fb, then p # q and by the definition of Z 1 we may assume p $! A. Since
Z1, 22,. . . ,Zk are mutually disjoint, Fz $! {Zl, Z 2 , .. . , ZI,},and hence, there is some s
with 2 5 s 5 b such that F, is in G1 for 1 5 i 5 s and Fs+l E {Zl, Z 2 , .. . , Z k}. This
implies that there is a path of length at most g - 2 joining p and a vertex w of A u
V(Q1)U V(Q2) U . . . U V(QkPl), where w and p are not in the same Q 3 ,which contradicts
(1) and (2). Therefore, the geometric-girth of G2 is at least g and G2 E N. But c(G2) =
c(G)+ 1, contradicting the maximality of c(G). Hence G E G(T,g, k).
I
By Lemma 1 and Theorem 1, we have the following which shows an ( r ,g,k)-cage
always exists.
Theorem 2.
For g 2 4 and k , r 2 2, there exists an (r,g, k)-cage with order
f ( r , g , k ) 5 k(k - 1)
r2
Z(r
-
l)i(k
-
1)Z
+ (r
-
l)g-Z(k
- 1)g-1
i=O
1
+ k.
3. KNOWN (c 9, &CAGES AND LOWER BOUNDS ON f(r, g, k)
We begin this section by showing an identity on the function f ( ~g,, k).
Define the clique graph C(G) of a graph G to be the graph whose vertices are the
cliques of G such that two vertices are adjacent if the corresponding two cliques intersect.
Let x ( r ,g, k ) denote the class of clique-disjoint graphs with geometric-girth g 2 4 which
26 JOURNAL OF GRAPH THEORY
have r cliques on each vertex and k vertices in each clique. Then it is easy to see that
if G E x(r,g, k ) with g 2 4, then C ( G ) E x(k,g, r ) . Moreover, if G has n vertices, then
C ( G )has n r / k vertices. Notice also that if G E x ( r ,g, k ) with g 2 4, then C ( C ( G ) )= G.
We have derived the following result extended to the current form by a referee.
Theorem 3. For g 2 4 and k , T 2 2, we have f ( k ,g, r ) = ( r / k ) f ( r g,
, k ) . Moreover, if G
is an ( r ,g, k)-cage, then C ( G )is a ( k ,g, r)-cage.
By setting k = 2 in the above theorem, we obtain the following connection between a
usual cage and a special generalized cage.
Corollary. For g 2 4, a graph G is an (r,g)-cage if and only if its line graph L ( G ) is a
(2, 9, r)-cage.
From now on, for g 2 4 and k , r 2 2, let
Then it is easy to see that f ( r , g, k ) 2 f ~ ( rg,
, k ) . Let G be a clique-disjoint [n,r ( k - l ) ,k 2]-semi-strongly regular graph with geometric-girth g. Define e = n - f o ( r ,g, k ) to be the
excess of G.
To examine [n,r ( k - l),k - 2)]-semi-strongly regular graphs with geometric-girth g
and excess 0 (i.e., an ( r ,g, k)-cage of order f O ( rg,
, k ) ) , we first introduce the concept of
generalized polygon due to J. Tits and given in [5]. An incidence plane consists of two
types of elements, “points” and “lines,” and a relation of “incidence” such that a point
may or may not be incident with a line. A chain of length n from two elements e and
f of an incidence plane is a sequence e = eo,e l , . . . , elL= f containing points and lines
alternatively such that e, is incident with e,+l for i = 0 , 1 , . . . ,n - 1. A nondegenerate
generalized g-gon G P ( r ,k , g) is an incidence plane such that
(i) each point is incident with r lines,
(ii) each line is incident with k points,
(iii) for each pair e, f of elements, there exists a chain of length at most g and there
exists at most one chain of length less than g from e to f , and
(iv) every element belongs to a closed chain of length 29.
A nondegenerate generalized 4-gon GP(T,k , 4) is also called a generalized quadrangle
GQ(r,k ) . Define the point graph of a nondegenerate generalized g-gon GP(r,k , g) to be
the graph whose vertices are the points of GP(r,k , g) such that two vertices are adjacent
if the two points are on a line. Then we have the following correspondence which was
extended to the current form by the same referee.
Proposition 1. Let g 2 4 be even. An ( T , 9 , k)-cage G of order n = fo(r, g, k ) must be
the point graph of a nondegenerate generalized g-gon GP(r,k , g), and conversely.
Proof. Let g 2 4 be even. First, we note that a nondegenerate generalized g-gon
G P ( r ,k , g) must have exactly f o ( r ,g, k ) points. Let G be an ( r ,g, k)-cage of order n =
f o ( r ,g, k ) . Then every vertex of G is on a cycle of length g whose edges are from distinct
O N GENERALIZED CAGES 27
cliques. By viewing the vertices as points, cliques as lines in G so that a point is incident
with a line if the corresponding vertex is in the clique, we obtain an incidence plane P
satisfying the conditions (i), (ii), and (iv). Since G is a clique-disjoint graph of order
n = f o ( r ,g, k ) with geometric-girth 9, P must satisfy the condition (iii). Thus, P is a
nondegenerate generalized g-gon and G is the point graph of P. Conversely, let G be
the point graph of a nondegenerate generalized g-gon GP(T,k , 9 ) . Then G has f o ( r ,g, k )
vertices. By the conditions (i) and (ii), every vertex of G is in T cliques and every clique of
G has k vertices. By the condition (iii), G must be a clique-disjoint which then implies G is
~ ( -k1)-regular. Then the conditions (iii) and (iv) together imply that the geometric-girth
of G is 9. Thus, G is an (r,g, k)-cage or order n = f 0 ( r , g , k ) .
I
It is proved in [5] that a finite nondegenerate generalized g-gon can exist only for
g = 2 , 3 , 4 , 6 , 8 ,or 12. Thus, we have
Corollary.
#
For even g
4,6,8, and 12, an (r,g,k)-cage G must have order n
>
fo(r19,k ) .
+
For g = 4, there are generalized quadrangles GQ(T,k ) for the pairs ( T , k ) = (2, q I),
( q + 2 , Y), (Y,~ + 2 ) (q+1,
,
~$11,( y 2 + l , Y + I ) , ( y + l , $ + I ) , (y2++1, q 3 + 1 ) , and ( q 3 + I , y2
+ l ) , where q is a prime power (see [2]). For g = 6, there are nondegenerate generalized
6-gons G P ( r , k , 6 ) for pairs ( r , k ) = ( q + l , q + l ) , ( q ’ + l , q + l ) , and ( y + l , q 3 + l ) , where
q is a prime power. For g = 8, there are nondegenerate generalized 8-gons GP(T,k , 8) for
pairs ( T , k ) = (q2 1,y 1) and ( q + 1, q2 1),where q is an odd power of 2. Thus, the point
+ +
+
graphs of these nondegenerate generalized g-gons give the corresponding
g = 4,6, and 8.
Next we turn our attention to odd values of g.
(T,
g, k)-cages for
Proposition 2. Any (T, 5, k)-cage G of order n = fo(r,5, k ) is [n,~ ( k - 1 ) ,k - 2 , I]-strongly
regular. Moreover, T > k unless k = T = 2 .
Proof. Let G by an
(T,
5, k)-cage of order n = f 0 ( r ,5, k), where
fo(T,
5, k ) = 1
+ T ( k - 1)+
T(T -
l)(k
-
1)2.
We only need to verify the condition that every two nonadjacent vertices have exactly one
common neighbor. Since the geometric-girth of G is 5, every pair of nonadjacent vertices
have at most one common neighbor. Let u and u be two nonadjacent vertices. The set
N ( u ) of neighboring vertices of u contains ~ ( -k 1) elements. Then u is in the set W
of remaining vertices. Since G is of minimum order, every vertex of W is adjacent to
some vertex of N ( u ) . Therefore, u and u have exactly one common neighbor, and G is
[n,~ ( -k l ) ,k - 2, I]-strongly regular. To see that T > k unless k = T = 2, we first apply
Theorem 3 to obtain
Since f ~ ( r5,, k ) = 1+ ~ ( -k1)+ T ( T - l ) ( k - 1)2, the above inequality implies T 2 k . But,
for k = T > 2, the associated geometry would be a nondegenerate generalized pentagon,
whose nonexistence is shown by the Feit-Higman theorem in [5].
I
The following theorem shows that there exists no ( T , 5, k)-cage of order n = f o ( r ,5, k ) +
1 (i. e., with excess one).
28 JOURNAL OF GRAPH THEORY
Theorem 4. For k , T 2 2, there is no clique-disjoint [n,r(k
regular graph with geometric-girth 5 and excess one.
-
l),k
-
2)]-semi-strongly
Proof. Suppose, toe the contrary, that there is an [n,r(lc- l ) ,k - 21-semi-strongly
regular graph G with geometric-girth 5 and excess one. Then
n = 2 + ~ ( -k1)
+
T(T -
l ) ( k - 1)2.
For convenience, let A = k - 2 and a = r ( k - 1)(=T ( A + 1)). Then G is a-regular and
n = a’ - A a + 2. For CY = 2, we have k = r = 2 and the only [n,2,Oj-semi-strongly regular
graph with geometric-girth 5 is the cycle C5 on five vertices which has excess 0. Thus,
we assume a 2 3. Let A be the adjacency matrix of G. Then we obtain
A2 - ( A - l ) A - ( a - 1 ) 1 = J - B
where J is the n x n matrix all of whose entries are 1 and J - B - I is the adjacency
matrix of K(2,2, . . . ,2) with a suitable relabeling of G. It follows that n is even. But the
eigenvalues of h’(2,2,. . . , 2 ) are n - 2,0, -2 with multiplicities 1, n/2, n/2 - 1, respectively, J - B has eigenvalues n - 1, 1, -1 with multiplicities 1, n/2, n/2 - 1, respectively.
Any eigenvector of A having eigenvalue z must also be an eigenvector of J - B with
eigenvalue x2 - (A - 1). - ( a- 1). As A is real and symmetric, it must have one eigenvalue
satisfying
x2 - (A - 1). - ( a - 1) = n - 1
(which gives
5 =
a as n = a2 - A a + 2), n/2 eigenvalues satisfying
2 - (A - 1).
-
( a - 1) = 1,
1.e..
and n/2 - 1 eigenvalues satisfying
2 - ( A - 1).
- ( a - 1) = -1,
i.e.,
Suppose that the multiplicities of the distinct eigenvalues zl,
x2,z3,x4 for the adjacency
matrix A are a, b, c, d, respectively. Then
a+b=-
n
2
n
and c + d = - - 1 .
2
Since the trace of A is zero, we obtain the following identity:
a
A-1
s
+ 2 ( n - 1) + - ( a
2
-
b)
+ -2t ( c
-
d) = 0.
ON GENERALIZED CAGES
29
Considering A3, the number in each (2, 2)-entry gives the number of (2, i) walks of length
3. Since each triangle containing vertex 2 gives two such walks, the (i,i)-entry of A3 is
equal to
T
(
)
2
= Xa.
Thus,
tr(A3) = nXa.
On the other hand,
which leads to the following identity:
nXa = a 3 + (X - 1)3
+ 3(x - q S 2 2
8
+
3(X
-
1)2s
+ s3
( a - b)
8
+ 3(X
-
1)2t
8
+ t 3 (C
-
d).
By substituting s2 and t2 from (3) and (4) in the above identity we obtain
nXa
=
a3+
+[(A
(X
-
1)3
+ 3(x qa-
2
2
S
-
1)2 +a]-(. - b )
2
+[(A - 1)2+ a
-
t
2]-(c - d).
2
Now we consider the following four cases:
Case 1. Both s and t are rational, hence both integral. Since s2 - t2 = 8, we must have
5 2, contradicting
s = 3 and t = 1. Thus, by (3), we have (A -1)2+4a = 9 which implies a
the assumption a 2 3.
Case 2. Both s and t are irrational. First suppose that s and t are linearly dependent
over the rationals. Then s2 and t2 must have the same square-free-part p, which must
divide their difference 8. Then /3 can only be 2. Let s = u a and t = v a . We have
s2 - t2 = 2(u2- v2) = 8 which gives u2- w2 = 4. But there are no two positive integers
u and w with the difference of the squares equal to 4. Thus s and t must be linearly
x2 occur in pairs; so also
independent over rationals. This implies that the eigenvalues zl,
do the eigenvalues x3, x4. Since one of n/2 and n/2 - 1 is odd, this is impossible.
Case 3. s is irrational and t is rational. Then the eigenvalues z1,x2must occur in pairs
which implies that n/2 is even (i.e., 4 divides n) and a = b. Since
71
= a2 - Xa
+ 2 = (A + 1)2r2
-
X(X
+ 1). + 2
30 JOURNAL OF GRAPH THEORY
+
+
+
and 4 divides n, where a = T ( X l ) , we must have X 1 even and T odd. Moreover, X 1
can not be divisible by 4. It follows that X 1 = 2 (mod 41, i.e., X = 1 (mod 4).As a = b,
( 5 ) and (6) give
+
and
nXa = a3
+ (A
+ [(A
-
-
1)2
1)s + 3(X - l)a n
2
2
t
+ ( a a)]-(.
2
-
- d).
After simplifying the second identity above we have
2nXa - 2a2
+ 2(X
-
+
1)2a 2 4 0
-
2 ) - 3(X - 1 ) n a
+ ( A - l ) ( n+ 2 ) a
=
(A
-
l)(-n
+ 4)
(7)
which implies that a( ( X- l) ( n- 4) = (X-l)(a2-Xa-2),
i.e., a(2(X-l). Since cy = r(X+l),
wehave(X+1)12(X-l),i.e., (X+1)14.ThenX+l =1 ,2 ,o r4 .R e c a llth a t A = 1 (mod4).
Thus X = 1, which eliminates several terms in (7) and leaving 2na - 2a2 2a(a - 2) = 0.
That is r i a = 2a, a contradiction.
+
Case 4. s is rational and t is irrational. Then the eigenvalues x3,x4 appear in pairs.
That is c = d. Similar to Case 3, by combining (5) and (6) and simplifying the resulting
identities, we obtain
3(X
-
l)a
+2a
-
2 X a = X2
-
X
-
4
(8)
whichimplies that cuI(X2-X-4). S i n c e a : = r ( X + l ) , ( X+ l) lX2 -X -4 a n d s o (X+1)12.
Thus, X 1 = 1 or 2 , that is X = 0 or 1. For X = 0, (8) yields that Q = 4. But the (4,
5)-cage has 19 vertices which is greater than n = 18, a contradiction. For X = 1, it follows
from (8) that 0 = -4, also a contradiction.
Therefore, the theorem follows.
I
By letting X = 0 (i.e., k = 2), we obtain Brown’s result [ l ] as a corollary.
+
Corollary.
There are no r-regular graphs with excess one and girth 5.
We remark that there do exist clique-disjoint [n,r ( k - l ) ,k - 21-semi-strongly regular
graphs with geometric-girth 5 and excess two, in fact, the line graph L ( P ) of the Petersen
graph P (see Figure 1) is such a graph.
Finally, note that for g = 2d + 1, an ( T , 9 , k)-cage of order n = f 0 ( r ,g, k ) is a Moore
geometry of diameter d (see [6] for definition). It is known that there exists no nontrivial
Moore geometry of diameter greater than 2 (see [31, [61 and [7]). Thus, we have the
following proposition.
Proposition 3.
For g
= 2d
+ 1 2 7 and k ,
T
2 2 , f ( r ,g, k ) > f 0 ( r ,g , k ) .
ON GENERALIZED CAGES
31
ACKNOWLEDGMENTS
I would like to thank my advisor Allen J. Schwenk for his many valuable suggestions and
comments and his continuous help. I also would like to thank the referees whose many
helpful suggestions have significantly improved this article. In particular, the author is
grateful to one referee who extended Theorem 3 and Proposition 1 to the current form.
References
W. G. Brown, On the non-existence of a type of regular graphs of girth 5, Canad. J. Math. 19
(1967), 644-648.
Peter J. Cameron, Strongly regular graphs, in: Selected Topics in Graph Theory (eds. L. W.
Beineke and R. J. Wilson), Academic Press, New York (1978), 337-360.
R. M. Darnerell, On finite Moore geometries, 11, Math. Proc. Camb. Phil. Soc. 90 (1981), 3340.
P. Erdos and H. Sachs, Reguke graphen gegebener Taillenweite mit monimsler Knotenzahl,
Wiss.Z. Uni. Halle (Math. Nut.) 12 (1963), 251-257.
W. Feit and G. Higman, The nonexistence of certain generalized polygons, J. Algebra 1 (1964),
114-131.
F. J. Fuglister, On finite Moore geometries, J. Combinatorial Theory (A) 23 (1977), 187-197.
F, J. Fuglister, The nonexistence of Moore geometries of diameter 4, Discrete Mathematics 45
(1983), 229-238.
N. Sauer, On the existence of regular n-graphs with given girth, J. Combinatorid Theory 9
(1970), 144147.
P. K. Wong, Cages-a
Received August 2, 1994
survey, J. Graph Theory 6 (1982), 1-22.
Документ
Категория
Без категории
Просмотров
2
Размер файла
550 Кб
Теги
205
1/--страниц
Пожаловаться на содержимое документа