Leaves in Representation Diagrams of Bipartite Distance-Regular Graphs
MICHAEL S. LANG [email protected]
Mathematics Department, Bradley University 1501 W. Bradley Ave., Peoria, IL 61625 Received May 22, 2001; Revised January 27, 2003; Accepted February 10, 2003
Abstract. Letdenote a bipartite distance-regular graph with diameter D ≥ 3 and valencyk ≥ 3. Let θ0> θ1>· · ·> θDdenote the eigenvalues ofand letqi jh (0≤h,i,j≤D) denote the Krein parameters of. Pick an integerh(1≤h≤D−1). Therepresentation diagram=his an undirected graph with vertices 0,1, . . . ,D. For 0≤i,j≤D, verticesi,jare adjacent inwheneveri = jandqi jh =0. It turns out that in , the vertex 0 is adjacent tohand no other vertices. Similarly, the vertexDis adjacent toD−hand no other vertices. We call 0,Dthetrivialvertices of. Letldenote a vertex of. It turns out thatlis adjacent to at least one vertex of. We saylis aleafwheneverlis adjacent to exactly one vertex of. We showhas a nontrivial leaf if and only ifis the disjoint union of two paths.
Keywords: primitive idempotent, eigenvalue, association scheme, Q-polynomial, antipodal
1. Introduction
In recent research on distance-regular graphs, the following theme emerges. Letdenote a distance-regular graph and letE andF denote primitive idempotents of. When is the entrywise productE◦Fa linear combination of a “small” number of primitive idempotents of?
We refer the reader to the articles of MacLean [5–7], Pascasio [9–11], and the present author [4] for work on this theme. In this paper we consider the case whereE◦Fis a linear combination of F and one other primitive idempotent. To keep things simple, we assume is bipartite. Before we state our main result, we recall a bit of notation.
Let = (X,R) denote a bipartite distance-regular graph with diameter D ≥ 3 and valencyk ≥ 3. (Definitions are contained in the next section.) Let θ0 > θ1 >· · · > θD
denote the eigenvalues of. Recall thatθ0=kandθD= −k; we callθ0andθDthetrivial eigenvalues of. For 0≤ i ≤ D, letEi denote the primitive idempotent ofassociated withθi. Letqi jh (0≤h,i,j≤ D) denote the Krein parameters of. Recall that
Ei◦Ej = |X|−1
D
h=0
qi jhEh (0≤i,j ≤D),
where◦denotes entrywise multiplication.
Pick an integer h (1 ≤ h ≤ D−1). We recall therepresentation diagram = h
[12–14].is an undirected graph with vertices 0,1, . . . ,D. For 0≤i,j ≤ D, verticesi and jare adjacent inwheneveri = j andqi jh =0.
It turns out that in, the vertex 0 is adjacent tohand no other vertices. Similarly, the vertexDis adjacent toD−hand no other vertices. We call 0 andDthetrivialvertices of .
Letl denote a vertex of. As we see in the next section,l is adjacent to at least one vertex of. We saylis aleafwheneverlis adjacent to exactly one vertex of. Our main result is the following.
Theorem 1.1 Letdenote a bipartite distance-regular graph with diameter D≥3and valency k ≥3. Pick an integer h(1≤h ≤ D−1). The representation diagramhhas a nontrivial leaf if and only ifhis the disjoint union of two paths.
Hypercubes and doubled Odd graphs have representation diagrams satisfying the con- ditions of Theorem 1.1. At diameters greater than 5, these are the only such graphs known.
2. Preliminaries
Let = (X,R) denote a finite, undirected, connected graph, without loops or multi- ple edges, with vertex set X, edge set R, path-length distance function ∂, and diameter D := max{∂(x,y) : x,y ∈ X}. Letk denote a nonnegative integer. We say isregu- lar withvalency k whenever for allx ∈ X,|{z ∈ X : ∂(x,z) = 1}| = k. We sayis distance-regularwhenever for all integersh,i,j(0 ≤h,i,j ≤ D) and allx,y ∈ X with
∂(x,y) = h, the scalar phi j = |{z ∈ X : ∂(x,z) = i, ∂(y,z) = j}|is independent of xandy. For notational convenience, setci := p1ii−1(1≤i ≤ D),ai := p1ii (0≤i ≤D), bi :=pi1i+1(0≤i≤ D−1), andc0 :=0,bD:=0. For the rest of this section, suppose is distance-regular. To avoid trivialities, assumeD≥3 andk≥3. We observeis regular with valencyk=b0. Further, we observeci+ai+bi =kfor 0≤i ≤D.
We sayisbipartitewhenever there exists a partitionX =X+∪X−such that no edge joins two vertices in the same cell of the partition. Observeis bipartite if and only if ai =0 (0≤i ≤ D), and in this case,
ci+bi =k (0≤i ≤D). (1)
For the rest of this section, supposeis bipartite.
Let ∼denote the binary relation on X such that for any x,y ∈ X, we have x ∼ y whenever x = yor ∂(x,y) = D. We say isantipodal whenever∼is an equivalence relation.
LetRdenote the field of real numbers. ByMatX(R) we mean theR-algebra consisting of all matrices whose entries are inRand whose rows and columns are indexed byX.
For each integeri(0≤i ≤D), letAi denote the matrix inMatX(R) withx,yentry (Ai)x y =
1 if∂(x,y)=i,
0 otherwise (x,y∈ X).
Abbreviate A:= A1. We call Atheadjacency matrixof. LetMdenote the sub-algebra ofMatX(R) generated by A. We call M theBose-Mesner algebraof . By [1, Theorem 20.7],A0,A1, . . . ,ADis a basis forM.
By [2, Theorem 2.6.1], M has a second basis E0,E1, . . . ,EDsuch that EiEj =δi jEi
(0≤i,j ≤D). We callE0,E1, . . . ,EDthe(primitive) idempotentsof.
Observe there exists a sequence of scalarsθ0, θ1, . . . , θDtaken fromRsuch that
A=
D
i=0
θiEi.
We callθi theeigenvalueof associated withEi. Noteθ0, θ1, . . . , θD are distinct since A generates M. Throughout this paper, we assume the eigenvalues are labeled so that θ0> θ1>· · ·> θD. By [2, p. 82],θ0 =kandθD−i = −θi for 0≤i ≤D. We callθ0and θDthetrivialeigenvalues of.
Letθh denote an eigenvalue of and let Eh denote the associated idempotent. Since A0,A1, . . . ,ADis a basis forM, there exist real scalarsσ0, σ1, ..., σDsuch that
Eh =mh|X|−1
D
i=0
σiAi, (2)
wheremh =rankEh. We callσ0, σ1, ..., σDthecosine sequenceassociated withθh. By [2, p. 128],
ciσi−1+biσi+1=θhσi (0≤i ≤ D), (3) whereσ−1andσD+1denote indeterminates.
Let◦denote entrywise multiplication inMatX(R) and observe
Ai◦Aj =δi jAi (0≤i,j≤ D). (4)
This impliesMis closed under◦. SinceE0,E1, . . . ,EDis a basis forM, there exist scalars qi jh ∈R(0≤h,i,j≤ D) such that
Ei◦Ej = |X|−1
D
h=0
qi jhEh. (5)
We call theqi jh theKrein parametersof.
In the next two lemmas, we recall a few basic facts about the product◦and the Krein parameters.
Lemma 2.1 [9,Lemma3.3,Theorem3.6]Let=(X,R)denote a bipartite distance- regular graph with diameter D≥3.
(i) E0◦Ei = |X|−1Eifor0≤i ≤D.
(ii) ED◦Ei = |X|−1ED−ifor0≤i≤ D.
(iii) For1≤i,j ≤ D−1,Ei◦Ejis not a scalar multiple of a single idempotent of. Lemma 2.2 Letdenote a bipartite distance-regular graph with diameter D≥3.
(i) qi jh =qhj i(0≤h,i,j≤ D).
(ii) mhqi jh =miqij h=mjqhij (0≤h,i,j ≤D).
(iii) q0hj=δh j (0≤h,j ≤D).
(iv) qD jh =δh,D−j (0≤h,j ≤D).
(iii) qDD−−ih,j =qi jh (0≤h,i,j ≤ D).
Proof: (i) Immediate from (5). (ii) [2, Lemma 2.3.1(iv)] (iii) Immediate from Lemma 2.1(i). (iv) Immediate from Lemma 2.1(ii). (v) Taking the entrywise product of both sides of (5) withEDand applying Lemma 2.1(ii), we get the result.
Definition 2.3 [12] Letdenote a distance-regular graph with diameterD. Pick an integer h (0≤h≤ D). We define therepresentation diagram=h.is an undirected graph with vertices 0,1, . . . ,D. For 0≤i,j ≤ D, verticesi and jare adjacent inwhenever i = jandqi jh =0. We sometimes sayis the representation diagram associated with the eigenvalueθh.
LetCdenote a connected component of. We sayCis apathwhenever there exists an orderingv0, v1, . . . , vl of the vertices ofC such that for 0≤ i,j ≤ l, verticesvi, vj are adjacent inif and only if|i− j| =1.
Lemma 2.4 Letdenote a bipartite distance-regular graph with diameter D≥3. With reference to Definition2.3,the following hold.
(i) For0 ≤ h,i,j ≤ D,vertices i and j are adjacent inh if and only if D−i and D−j are adjacent inh.
(ii) 0has no edges.
(iii) InD,vertex i(0≤i≤ D)is adjacent to D−i and no other vertices.
(If D is even then vertex D/2is not adjacent to any vertices.)
(iv) Suppose h = 0. Inh,vertex 0 is adjacent to h and no other vertices. Moreover, vertex D is adjacent to D−h and no other vertices.
(v) Suppose1≤h≤ D−1. Each vertex ofhis adjacent to at least one other vertex.
Proof: (i)–(iv) Immediate from Lemma 2.2. (v) Letidenote a vertex ofhand supposeiis not adjacent to any vertices ofh. By (iv) above, we find 1≤i ≤D−1. By Definition 2.3,
qi jh = 0 for j = i. Applying Lemma 2.2(ii),we findqhij =0 for j = i, which implies Eh◦Ei is a scalar multiple ofEi. This contradicts Lemma 2.1(iii).
We call 0 andDthetrivialvertices of a representation diagram.
Lemma 2.5 Letdenote a bipartite distance-regular graph with diameter D ≥ 3and valency k≥3. The following are equivalent for1≤h ≤D−1.
(i) his not connected.
(ii) is antipodal and h is even.
Suppose(i)–(ii)hold. Thenhhas two connected components,one consisting of the even vertices and one consisting of the odd vertices.
Proof: Letσ0, σ1, ..., σDdenote the cosine sequence associated withθh.
(i)→(ii) Sinceh is not connected and by [2, Proposition 2.11.1],σi =1 for somei (1 ≤i ≤ D). By [2, Proposition 4.4.7],is antipodal andσD =1. Nowhis even by [2, p. 142].
(ii)→(i) By [2, p. 142],σD=1. Nowhis not connected by [2, Proposition 2.11.1].
Suppose (i)–(ii) hold. We already mentionedσD =1. By [2, Proposition 4.4.7],σi =1 for 1≤i ≤ D−1. Now by [2, Proposition 2.11.1],hhas two components. By [2, p. 413], qi jh =0 if one ofi andj is even and the other is odd. The result follows.
Example 2.6 Letdenote a bipartite distance-regular graph with diameter 3 and valency k≥3. With reference to Definition 2.3, the following hold.
(i) 1is the path 0, 1, 2, 3.
(ii) Supposeis not antipodal. Then2is the path 0, 2, 1, 3.
(iii) Supposeis antipodal. Then2is the disjoint union of the paths 0, 2 and 1, 3.
Proof: (i) By Lemma 2.4(iv), vertex 0 is adjacent to 1 and no other vertices. Also, vertex 3 is adjacent to 2 and no other vertices. By Lemma 2.5,1is connected, so 1 is adjacent to 2 and we are done.
(ii), (iii) Similar to the proof of (i).
3. Leaves
Definition 3.1 Letdenote a bipartite distance-regular graph with diameterD≥3 and valencyk ≥ 3. Fixh (1≤ h ≤ D−1) and let =h denote a representation diagram of. Letl denote a vertex of. By Lemma 2.4(v),lis adjacent to at least one vertex of . We saylis aleafwheneverlis adjacent to exactly one vertex of. Observelis a leaf if and only if there exists an idempotentFofwithF =Elsuch that
Eh◦El ∈Span{El,F}. (6)
By Lemma 2.4,lis a leaf if and only ifD−lis a leaf. Also, the trivial vertices 0 andDof are leaves.
Theorem 3.2 Letdenote a bipartite distance-regular graph with diameter D≥3and valency k ≥3. Leth(1 ≤ h ≤ D−1)denote a representation diagram of. Suppose h has at least one nontrivial leaf. Then the following hold.
(i) h is the disjoint union of two paths, one consisting of the even vertices and one consisting of the odd vertices.
(ii) is antipodal and h is even.
Proof: We abbreviate:=h.
(i) IfD=3 the result follows from Example 2.6, so supposeD≥4. Letσ0, σ1, ..., σD
denote the cosine sequence associated with θh. We show there exists β ∈ R such that σi−1−βσi+σi+1is independent ofi for 1≤i≤ D−1.
By assumption,has a nontrivial leaf. Let us denote this leaf byl. Lettdenote the vertex ofto whichlis adjacent. Apparently,t =land there exist, ζ ∈Rwithζ =0 such that
Eh◦El =El+ζEt. (7)
Letρ0, ρ1, . . . , ρDandτ0, τ1, . . . , τDdenote the cosine sequences associated withθl and θt, respectively. We use (2) to eliminateEh,ElandEt from (7) and then apply (4). In the result, we equate coefficients of Ai and simplify to find that for 0≤i ≤D,
σiρi =xρi+yτi, (8)
wherex= |X|m−1h andy= |X|mtm−1h m−1l ζ. Notey=0 becauseζ =0.
We use (8) for 0≤i ≤4. Repeatedly applying (3) and (1), we find for 0≤i ≤4 that σi = fi(θh),ρi = fi(θl) andτi = fi(θt), where the functions fiare given by
f0(λ)=1, f1(λ)= λ
k, f2(λ)=λ2−k
kb1 , (9)
f3(λ)= λ3−(k+c2b1)λ
kb1b2 , f4(λ)= λ4−(k+c2b1+c3b2)λ2+c3kb2
kb1b2b3 . (10) We seti =0,1 in (8) to obtain two linear equations inxandy. To solve this system, we first verify the coefficient matrix is nonsingular. This coefficient matrix is
ρ0 τ0
ρ1 τ1
. (11)
Evaluating the determinant of (11) using (9), we find this determinant equals (θt−θl)k−1. This is nonzero, so the coefficient matrix is nonsingular. We now solve the system of equations to find in view of (9) that
x=θhθl−θtk
k(θl−θt), y=θl(k−θh)
k(θl−θt). (12)
Noteθlis a factor ofyand so cannot be zero. We seti =2 in (8), apply (9) and (12) and solve forθtto get
θt= θl2θh+θl2−θhk−k2 b1θl
. (13)
We seti =3 in (8), apply (9)–(10), (12) and (13), and simplify to find k2−θh2
k2−θl2
θlk2b31b22
(b2−(c2−1)θh)θl2−b2(k+θh)
=0. (14)
The fraction is nonzero andb2(k+θh)=0, sob2−(c2−1)θh =0. We solve (14) forθl2
to get
θl2= (k+θh)b2 b2−(c2−1)θh
. (15)
We seti =4 in (8) and apply (9)–(10), (12), (13) and (15) to find the left side minus the right is
k2−θh2
(k+θh) k2−θl2
c2
θl2(b2−(c2−1)θh)2k2b21b2b32 (16) times
(b2−b3)θh3+(b2−b3c2)θh2+
2b3b2−b3c2b2−b22
θh+b22(b3−1). (17) Since (16) is nonzero, (17) must be zero.
By [3, Lemma 9.3] and since (17) is zero, there existsβ ∈Rsuch thatσi−1−βσi+σi+1
is independent ofifor 1≤i ≤ D−1. Now, by [4, Theorem 5.4], eitheris a path or is as in (i). Sincehas a nontrivial leaf,cannot be a path. Sois as in (i), as desired.
(ii) By (i),is not connected. Now the result follows by Lemma 2.5.
Example 3.3 Letdenote a bipartite antipodal distance-regular graph with diameter 4 and valencyk≥3. With reference to Definition 2.3, the following hold.
(i) 2is the disjoint union of the paths 0, 2, 4 and 1, 3.
(ii) Supposeh =1 orh =3. Thenhhas no nontrivial leaves.
Proof: (i) Immediate from Lemma 2.4(iv) and Lemma 2.5.
(ii) Sincehis odd,hhas no nontrivial leaves by Theorem 3.2.
Example 3.4 Letdenote a bipartite antipodal distance-regular graph with diameter 5 and valencyk≥3. With reference to Definition 2.3, the following hold.
(i) 2is the disjoint union of the paths 0, 2, 4 and 5, 3, 1.
(ii) 4is the disjoint union of the paths 0, 4, 2 and 5, 1, 3.
(iii) Supposeh=1 orh =3. Thenhhas no nontrivial leaves.
Proof: (i) By Lemma 2.5, the even vertices of2 comprise a connected component.
This component consist of the path 0, 2, 4 since vertex 0 is adjacent to 2 but not 4 by Lemma 2.4(iv). Now the odd vertices form the path 5, 3, 1 by Lemma 2.4(i).
(ii) Similar to the proof of (i).
(iii) Sincehis odd,hhas no nontrivial leaves by Theorem 3.2.
In the next lemma and the following two examples, we recall some information about theD-cube.
Lemma 3.5[2,Section9.2] Letdenote the D-cube.
(i) is antipodal.
(ii) For0≤h,i,j ≤D, qi jh =0if|i− j| =h and qi jh =0if|i−j|>h.
Example 3.6 LetDdenote an odd integer withD≥3 and letdenote theD-cube. With reference to Definition 2.3, the following hold.
(i) 2is the disjoint union of the paths 0,2,4, . . . ,D−1 and 1,3,5, . . . ,D.
(ii) D−1is the disjoint union of the paths 0,D−1,2,D−3, . . .andD,1,D−2,3, . . .. (iii) Supposeh=2 andh =D−1. Thenhhas no nontrivial leaves.
Proof: (i) is antipodal by Lemma 3.5(i), so by Lemma 2.5, 2 has two connected components, one consisting of the even vertices and one consisting of the odd vertices. For 0≤i,j ≤D, we see by Lemma 3.5(ii) thatqi j2 =0 if|i−j| =2 andqi j2 =0 if|i−j|>2.
The result follows.
(ii) We mentionedis antipodal, so by Lemma 2.5,D−1has two connected components, one consisting of the even vertices and one consisting of the odd vertices. For 0≤i,j ≤D, we see by Lemma 3.5(ii) thatqi j1 =0 if|i−j| =1 andqi j1 =0 if|i− j|>1. Applying Lemma 2.2(v), we then getqDD−−1i,j =0 if|i− j| =1 andqDD−−1i,j =0 if|i− j|>1. The result follows.
(iii) Follows from Theorem 3.2, [4, Theorem 5.4]and [3, Example 17.1]
Example 3.7 Let Ddenote an even integer with D ≥ 4 and letdenote the D-cube.
With reference to Definition 2.3, the following hold.
(i) 2is the disjoint union of the paths 0,2,4, . . . ,Dand 1,3,5, . . . ,D−1.
(ii) Supposeh =2. Thenhhas no nontrivial leaves.
Proof: (i) By Lemma 2.5,2has two connected components, one consisting of the even vertices and one consisting of the odd vertices. For 0≤i,j ≤D, we see by Lemma 3.5(ii) thatqi j2 =0 if|i− j| =2 andqi j2 =0 if|i−j|>2. The result follows.
(ii) Follows from Theorem 3.2, [4, Theorem 5.4]and [3, Example 17.1].
Theorem 3.8 Letdenote a bipartite distance-regular graph with diameter D≥3and valency k ≥ 3. Let = h (1 ≤ h ≤ D−1) denote a representation diagram of. Supposehas a nontrivial leaf. Supposeis not one of Examples2.6, 3.3, 3.4, 3.6, 3.7.
Then either(a)D is odd and h=D−1or(b)D≡1(mod4)and h=(D−1)/2. In case (a)the nontrivial leaves are(D−1)/2and(D+1)/2. In case(b)the nontrivial leaves are 1and D−1.
Proof: Letldenote a nontrivial leaf of. ThenD−lis also a leaf. ReplacinglbyD−l if necessary, we assumel≤ D/2. RecallEh◦Elis a linear combination ofEland one other idempotent of. By [7, Lemma 4.4],is either 2-homogeneous in the sense of Nomura [8] or taut in the sense of MacLean [7].
First supposeis 2-homogeneous. By [8, Theorem 1.2], eitheris antipodal withD≤5 oris theD-cube. But this impliesis as in one of the examples we excluded.
Next supposeis taut andDis even. Setd := D/2. By [7, Theorem 4.3],l is either 1 ord. By [7, Corollary 6.6],l =d−1. Combining these facts, we findl=1 andd =2. Now D =2d =4. Recallis antipodal by Theorem 3.2(ii). Nowis as in Example 3.3(ii), which is a contradiction.
Finally, supposeis taut andDis odd. Setd :=(D−1)/2. By Theorem 3.3(ii),his even. By [7, Theorem 4.3], the ordered pair (h,l) is one of (D−1,d), (d,1), and (D−d,1).
First suppose (h,l) =(D−1,d). Then we have (a). Next suppose (h,l) =(d,1). Since D =2d +1 and sinced =h is even, we have (b). Finally, suppose (h,l)=(D−d,1).
By [7, Theorem 6.2, Corollary 6.3],ED−d◦E1 ∈Span{ER,ES}for someR,Ssuch that 1<S <R. But this contradicts (6).
Note 3.9 The doubled Odd graph 2.Ok is the only known graph for which (a) holds in Theorem 3.8. There is no known graph for which (b) holds.
Acknowledgment
This paper is part of the author’s dissertation, written at the University of Wisconsin–
Madison under the direction of Paul Terwilliger.
The author would like to thank the anonymous referees for their helpful comments.
References
1. N. Biggs,Algebraic Graph Theory, 2nd edition, Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1993.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier,Distance-regular graphs, volume 18 ofErgebnisse der Math- ematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1989.
3. M.S. Lang, “A new inequality for bipartite distance-regular graphs.”J. Combin. Theory Ser. B. Submitted.
4. M.S. Lang, “Tails of bipartite distance-regular graphs,”European J. Combin.23(8) (2002), 1015–1023.
5. M.S. MacLean, “Taut distance-regular graphs of odd diameter,”J. Algebraic Combin.,17(2).
6. M.S. MacLean. “Taut distance-regular graphs with even diameter,”J. Combin. Theory Ser. B. Submitted.
7. M.S. MacLean, “An inequality involving two eigenvalues of a bipartite distance-regular graph,”Discrete Math.225(1–3): (2000), 193–216. Formal power series and algebraic combinatorics (Toronto, ON, 1998).
8. K. Nomura, “Spin models on bipartite distance-regular graphs,”J. Combin. Theory Ser. B64(2) (1995), 300–313.
9. Arlene A. Pascasio, “Tight graphs and their primitive idempotents,”J. Algebraic Combin.10(1) (1999), 47–59.
10. A.A. Pascasio, “An inequality on the cosines of a tight distance-regular graph,”Linear Algebra Appl.325(1-3) (2001), 147–159.
11. A.A. Pascasio, “Tight distance-regular graphs and theQ-polynomial property,”Graphs Combin.17(1) (2001), 149–169.
12. P. Terwilliger, “A characterization ofP- andQ-polynomial association schemes,”J. Combin. Theory Ser. A, 45(1) (1987), 8–26.
13. P. Terwilliger, “Balanced sets andQ-polynomial association schemes,”Graphs Combin.,4(1) (1988), 87–94.
14. P. Terwilliger, “A new inequality for distance-regular graphs,”Discrete Math.137(1–3) (1995), 319–332.
