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.

1/--страниц