Leaves in Representation Diagrams of Bipartite Distance-Regular Graphs
Michael S. Lang
DOI: 10.1023/B:JACO.0000011939.15842.26
Abstract
Let 
denote a bipartite distance-regular graph with diameter D 
3 and valency k 3. Let 
0 > 1 ;;; > D denote the eigenvalues of and let q h ij (0 
h, i, j D) denote the Krein parameters of . Pick an integer h (1 h D - 1). The representation diagram 
= h is an undirected graph with vertices 0,1,..., D. For 0 i, j D, vertices i, j are adjacent in whenever i 
j and q h ij 0. It turns out that in , the vertex 0 is adjacent to h and no other vertices. Similarly, the vertex D is adjacent to D - h and no other vertices. We call 0, D the trivial vertices of . Let l denote a vertex of . It turns out that l is adjacent to at least one vertex of . We say l is a leaf whenever l is adjacent to exactly one vertex of . We show has a nontrivial leaf if and only if is the disjoint union of two paths.
denote a bipartite distance-regular graph with diameter D 3 and valency k 3. Let 0 > 1 ;;; > D denote the eigenvalues of and let q h ij (0 h, i, j D) denote the Krein parameters of . Pick an integer h (1 h D - 1). The representation diagram = h is an undirected graph with vertices 0,1,..., D. For 0 i, j D, vertices i, j are adjacent in whenever i j and q h ij 0. It turns out that in , the vertex 0 is adjacent to h and no other vertices. Similarly, the vertex D is adjacent to D - h and no other vertices. We call 0, D the trivial vertices of . Let l denote a vertex of . It turns out that l is adjacent to at least one vertex of . We say l is a leaf whenever l is adjacent to exactly one vertex of . We show has a nontrivial leaf if and only if is the disjoint union of two paths.Pages: 245–254
Keywords: primitive idempotent; eigenvalue; association scheme; Q-polynomial; antipodal
Full Text: PDF
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 of Ergebnisse der Mathematik 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). LANG
8. K. Nomura, “Spin models on bipartite distance-regular graphs,” J. Combin. Theory Ser. B 64(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 the Q-polynomial property,” Graphs Combin. 17(1) (2001), 149-169.
12. P. Terwilliger, “A characterization of P- and Q-polynomial association schemes,” J. Combin. Theory Ser. A, 45(1) (1987), 8-26.
13. P. Terwilliger, “Balanced sets and Q-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.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-regular graphs, volume 18 of Ergebnisse der Mathematik 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). LANG
8. K. Nomura, “Spin models on bipartite distance-regular graphs,” J. Combin. Theory Ser. B 64(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 the Q-polynomial property,” Graphs Combin. 17(1) (2001), 149-169.
12. P. Terwilliger, “A characterization of P- and Q-polynomial association schemes,” J. Combin. Theory Ser. A, 45(1) (1987), 8-26.
13. P. Terwilliger, “Balanced sets and Q-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.