Health & Medicine

6 pages
11 views

Bipartite Q-polynomial quotients of antipodal distance-regular graphs

of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Bipartite Q-polynomial quotients of antipodal distance-regular graphs
Transcript
  Journal of Combinatorial Theory, Series B  76 , 291296 (1999) Bipartite  Q- Polynomial Quotients of AntipodalDistance-Regular Graphs John S. Caughman, IV Department of Mathematics ,  Michigan State University ,  East Lansing ,  Michigan  48824 - 1027  E-mail: caughman  math.msu.eduReceived October 15, 1998Let  1   denote a bipartite  Q- polynomial distance-regular graph with diameter D 4. We show that  1   is the quotient of an antipodal distance-regular graph if andonly if one of the following holds.(i)  1   is a cycle of even length.(ii)  1   is the quotient of the 2 D- cube.   1999 Academic Press 1. INTRODUCTIONLet  1   denote a distance-regular graph with diameter  D 3 (definitionsappear in Section 2). Suppose  1   is  Q- polynomial with respect to someprimitive idempotent, and let  % 0 *,  % 1 *, ...,  % * D  denote the associated dualeigenvalue sequence. By Leonard [9], this sequence satisfies % * i  &1 &(  ; +1)  % i  *+(  ; +1)  % * i  +1 & % * i  +2 =0 (0< i  < D &1), (1)for some real scalar  ; . We use (1) at  i  = D &1 to define  % * D +1 ; that is, weset % * D +1  := % * D &2 &(  ; +1)  % * D &1 +(  ; +1)  % * D . (2)Suppose  1   is bipartite with  D 4, and  1   is the quotient of an antipodaldistance-regular graph  1  $. Then  1  $ has even diameter [2, p. 141], and byTerwilliger [10],  1   must satisfy  % * D &1 = % * D +1 . In this article, we considerthe implications of these results, and our main results are the following.1 . 1 . Theorem.  Let 1 denote a bipartite distance-regular graph withdiameter D 3  and valency k 3.  Suppose 1 is Q-polynomial with respect tosome primitive idempotent E  .  Let % 0 *, ...,  % * D  denote the associated dual eigen-value sequence ,  and let ; ,  % * D +1  be as in  (1), (2).  Suppose % * D &1 = % * D +1 . Article ID jctb.1999.1911, available online at http:   www.idealibrary.com on 291 0095-8956   99   30.00 Copyright  1999 by Academic PressAll rights of reproduction in any form reserved.  Then either 1 is the quotient of the  2 D-cube ,  or else D =3,  ; 2,  and theintersection numbers are given byc 2 =  ; ,  c 3 =  ; (  ; +1). (3)1 . 2 . Corollary.  Let 1 denote a bipartite Q-polynomial distance-regular graph with diameter D 4.  Then 1 is the quotient of an antipodal distance - regular graph if and only if one of the following holds .(i)  1 is a cycle of even length .(ii)  1 is the quotient of the  2 D-cube .The proofs of Theorem 1.1 and Corollary 1.2 are contained in Section 3.2. PRELIMINARIESIn this section, we collect only those definitions necessary to state andprove our results. For a more complete introduction to distance-regulargraphs, we refer to [1] or [2]. Let  1  =( X  ,  R ) denote a finite, connected, undirected graph, withoutloops or multiple edges, with vertex set  X  , edge set  R , path-length distancefunction , and diameter  D  :=max [ ( x ,  y ) |  x ,  y  #  X] . For each  x  #  X   andeach integer  i  , set  1  i  ( x ) := [y  #  X   | ( x ,  y )= i] .  1   is said to be  bipartite whenever there exists a partition  X  = X  + _ X  & such that the graphsinduced on  X  + and  X  & contain no edges.  1   is said to be  distance-regular ,with  intersection numbers c i  ,  b i   (0 i   D ), whenever for all integers  i  (0 i   D ) and for all  x ,  y  #  X   with ( x ,  y )= i  , we have | 1  i  &1 ( x ) & 1  1 (  y )|= c i  , and | 1  i  +1 ( x ) & 1  1 (  y )|= b i  . Following convention, we set  +  := c 2 , and we refer to  k  := b 0  as the  valency  of   1  . We say  1   is  antipodal  if the relation  R 0,  D  := [xy  | ( x ,  y )=0 or  D]  is an equivalence relation on X  . When  1   is antipodal, we define the  quotient  of   1   to be the graph whosevertices are the equivalence classes of   R 0,  D , and where two classes are adja-cent whenever they contain adjacent vertices of   1  .For the rest of this article, we assume that  1   is bipartite and distance-regular. It is well known that  c i  + b i  = k  (0 i   D ), and we observe that b D =0, so  k = c D .We now recall the BoseMesner algebra of   1  . Let Mat X  (C) denote thealgebra of matrices over C with rows and columns indexed by  X  . For0 i   D , let  A i   denote the matrix in Mat X  (C) with  x ,  y  entry( A i  ) xy = { 1 if ( x ,  y )= i  0 if ( x ,  y ){ i   ( x ,  y  #  X  ).292  JOHN S. CAUGHMAN, IV  Note that  A 1  is the adjacency matrix for  1  , and  A 0 , ...,  A D  form a basis fora subalgebra  M   of Mat X  (C), known as the  Bose  Mesner algebra .  M   iscommutative and semisimple; in particular,  M   has a basis  E  0 , ...,  E  D  of mutually orthogonal primitive idempotents. We refer to  E  0 , ...,  E  D  as the  primitive idempotents  of   1  . Let  E   denote any primitive idempotent of   1  ,and write  E  =| X  | &1  Di  =0  % i  * A i  . We refer to  % 0 *,  % 1 *, ...,  % * D  as the  dual eigenvalue sequence  associated with  E  . We note that  % 0 * equals the rank of  E   and is therefore nonzero [1, p. 62]. By the  eigenvalue of A 1  associated with E  , we mean the real scalar  %  satisfying  A 1 E  = %E  .Finally, let  E   denote a primitive idempotent of   1  . Observe  M   is closedunder entry-wise multiplication.  1   is said to be  Q-polynomial with respectto E   whenever there exists an ordering  E  0 , ...,  E  D  of the primitive idem-potents such that for each  i   (0 i   D ), the matrix  E  i   is an entry-wise poly-nomial of degree exactly  i   in  E  . In particular, if   1   is  Q- polynomial withrespect to  E  , then  E  1 = E   and  E  0  is a multiple of the all-ones matrix.Furthermore, the dual eigenvalues associated with  E   must be distinct[1, p. 263]. We say  1   is  Q-polynomial   whenever  1   is  Q- polynomial withrespect to at least one primitive idempotent.3. PROOFS OF THE MAIN RESULTSLet  1   denote a bipartite distance-regular graph with diameter  D 3. Let E   denote any primitive idempotent for  1  , and let  % 0 *, ...,  % * D  denote theassociated dual eigenvalue sequence. It is well known (cf. [2, p. 128]) that c i  % * i  &1 + b i  % * i  +1 = %% i  * (0 i   D ), (4)where  %  denotes the eigenvalue of   A 1  associated with  E  , and where  % * &1 , % * d  +1  are indeterminates. Setting  i  =0 in (4) yields  % = k% 1 * % 0 *. Applyingthis to (4) with  i  = D  yields % 0 * % * D &1 = % 1 * % * D . (5)Now assume  1   is  Q- polynomial with respect to  E  . Then the dual eigen-values are distinct, so substituting  b i  = k & c i   into (4) and again eliminating % , we obtain c i  =  k% 0 *  \ % 1 * % i  *& % 0 * % * i  +1 % * i  &1 & % * i  +1  +  (1 i   D &1). (6)293 BIPARTITE QUOTIENTS OF DRGs  Setting  i  =1 in (6), we find that  % 21 *{ % 0 * % 2 *, and k = % 0 *( % 0 *& % 2 *) % 21 *& % 0 * % 2 * . (7)Using these equations, we obtain the following.3 . 1 . Lemma.  With the notation and assumptions of Theorem  1.1,(i)  Assume ; =2.  Thenc i  = i   (1 i  < D );  c D = k =2 D . (8)(ii)  Assume ; {2.  Thenc i  =( q D + q )( q i  &1)( q &1)( q D + q i  ) (1 i  < D );  c D = k =( q D + q )( q D &1)( q &1)  q D  , (9) where q + q &1 =  ; .  Moreover ,  the denominators in  (9)  are nonzero . Proof  . (i) By the recurrence (1), the quantity  % * i  &1 &  ;% i  *+ % * i  +1  isindependent of   i  , so % i  *= h 1 + h 2 i  + h 3 i  2 (0 i   D +1), (10)for some complex scalars  h 1 ,  h 2 ,  h 3 . But  % * D +1 = % * D &1 , so  h 2 =&2 Dh 3 .Observe  h 3 {0; otherwise  h 2 =0, forcing  % 0 *= % 1 *. So evaluating (5), wefind 2 h 1 = D (2 D &1)  h 3 . Eliminating  h 1 ,  h 2  in (10) and substituting into(6), (7) we obtain (8).(ii) If   ; =&2, then since  % * D +1 = % * D &1 , (2) implies  % * D = % * D &2 ,a contradiction. So  ;    [ 2, &2 ] . By the recurrence (1), the quantity % * i  &1 &  ;% i  *+ % * i  +1  is independent of   i  , so there exist complex scalars  h 1 ,  h 2 , h 3  such that % i  *= h 1 + h 2 q i  + h 3 q & i  (0 i   D ), (11)where  q + q &1 =  ; . But  % * D +1 = % * D &1 , so  h 2 = h 3 q &2 D . Observe  h 3 {0;otherwise  h 2 =0, forcing  % 0 *= % 1 *. Now by (5) and (11),0= % 0 * % * D &1 & % 1 * % * D % 0 *& % * D =( q &1)( h 1 q D ( q D + q )+ h 3 ( q +1)( q D +1)) q D +1 ( q D &1) .Observe  q &1 is nonzero since  ; {2, so the above implies  h 1 =& h 3 ( q +1)(1+ q & D )( q D + q ) &1 . Eliminating  h 1 ,  h 2  in (11) and substitutinginto (6), (7) we obtain (9).  K 294  JOHN S. CAUGHMAN, IV  3 . 2 . Lemma.  With the notation and assumptions of Theorem  1.1,(i)  + 2,  and  ; +2=  + 2  + &1 k &2 k &  + . (12)(ii)  ; 2,  and ; is an integer . Proof  . (i) First assume  ; =2. Then  + =2,  k =2 D  by Lemma 3.1(i),and (12) follows. Next assume  ; {2. Lemma 3.1(ii) implies  + 2 ( k &2)=(  ; +2)(  + &1)( k &  + ). (13)We are assuming  k 3, so neither side of (13) is zero, and  + 2. Now (13)implies (12).(ii) Since  + 2, the first factor on the right side of (12) is at least 4,and the second factor is at least 1. It follows that the right side of (12) isat least 4, so  ; 2.To see that  ;  is an integer, assume  ; >2. Define polynomials  T  0 ,  T  1 , T  2 , ... in Z[ * ] by  T  0 =2,  T  1 = * , and  T  i  +1 = *T  i  & T  i  &1  (1 i  <  ). Aneasy induction shows that  T  i  (  ; )= q i  + q & i  for  i  0, where  q + q &1 =  ; .Moreover,  T  i   is monic of degree  i   for  i  1. Expanding  k  using (9), we find k =  D &1 i  =0  T  i  (  ; ), so  ;  is a root of   p ( * ) :=  D &1 i  =0  T  i  ( * )& k . Thus,  ;  is analgebraic integer. But  ;  is rational by (12), so  ;  is an integer.  K Proof of Theorem  1.1. Recall  ; 2 by Lemma 3.2(ii). If   ; =2, then byLemma 3.1(i) and Brouwer [2, p. 264],  1   is either the quotient of the2 D- cube, or else  D =3 and line (3) holds as desired.We now assume  ; >2, and show  D =3. By way of contradiction,suppose  D >3. Set  n =(  ; &  + +1)(  ; &  + ). By (9) with  i  =2, n =(1& q )( q D + q 4 )( q D & q 3 )( q D +1 + q 3 ) 2  , (14)where  q + q &1 =  ; . We claim  n <0. By Lemma 3.2(ii),  q  is a positive realnumber, and  q {1 since  ; {2. If 0< q <1, the first two factors in thenumerator of (14) are positive, and the third is negative, so  n <0. If   q >1,the first factor in the numerator of (14) is negative, and the second twofactors are positive, so  n <0.In either case,  n <0. But by Lemma 3.2(ii),  n  is nonnegative (being aproduct of consecutive integers), so we have a contradiction. It follows that D =3. Setting  D =3 in Lemma 3.1(ii), we get line (3).  K Proof of Corollary  1.2. Suppose  1   is the quotient of an antipodal dis-tance-regular graph. First assume  k =2. Then  1   is a cycle of even length.295 BIPARTITE QUOTIENTS OF DRGs
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks