Pseudo 1-homogeneous distance-regular graphs
Aleksandar Jurišić1
and Paul Terwilliger2
1University of Ljubljana Faculty of Computer and Informatic Sciences Ljubljana Slovenia
2University of Wisconsin-Madison Department of Mathematics Madison WI 53706-1388 USA
2University of Wisconsin-Madison Department of Mathematics Madison WI 53706-1388 USA
DOI: 10.1007/s10801-007-0115-y
Abstract
Let Γ be a distance-regular graph of diameter d\geq 2 and a 1\neq 0. Let θ be a real number. A pseudo cosine sequence for θ is a sequence of real numbers σ 0,\cdots , σ d such that σ 0=1 and c i σ i - 1+ a i σ i + b i σ i+1= θ σ i for all i\in {0,\cdots , d - 1}. Furthermore, a pseudo primitive idempotent for θ is E θ = s\thinspace \sum i=0 d σ i A i , where s is any nonzero scalar. Let [^( v)] \hat{v} be the characteristic vector of a vertex v\in VΓ . For an edge xy of Γ and the characteristic vector w of the set of common neighbours of x and y, we say that the edge xy is tight with respect to θ whenever θ \neq k and a nontrivial linear combination of vectors E[^( x)] E\hat{x} , E[^( y)] E\hat{y} and Ew is contained in Span{[^( z)] | z Ĩ V G, {\P}( z, x)= d= {\P}( z, y)} \mathrm{Span}\{\hat{z}\mid z\in V{Γ},\
tial(z,x)=d=
tial(z,y)\} . When an edge of Γ is tight with respect to two distinct real numbers, a parameterization with d+1 parameters of the members of the intersection array of Γ is given (using the pseudo cosines σ 1,\cdots , σ d , and an auxiliary parameter ϵ ).
tial(z,x)=d=
tial(z,y)\} . When an edge of Γ is tight with respect to two distinct real numbers, a parameterization with d+1 parameters of the members of the intersection array of Γ is given (using the pseudo cosines σ 1,\cdots , σ d , and an auxiliary parameter ϵ ).
Let S be the set of all the vertices of Γ that are not at distance d from both vertices x and y that are adjacent. The graph Γ is pseudo 1 -homogeneous with respect to xy whenever the distance partition of S corresponding to the distances from x and y is equitable in the subgraph induced on S. We show Γ is pseudo 1-homogeneous with respect to the edge xy if and only if the edge xy is tight with respect to two distinct real numbers. Finally, let us fix a vertex x of Γ . Then the graph Γ is pseudo 1-homogeneous with respect to any edge xy, and the local graph of x is connected if and only if there is the above parameterization with d+1 parameters σ 1,\cdots , σ d , ϵ and the local graph of x is strongly regular with nontrivial eigenvalues a 1 σ /(1+ σ ) and ( σ 2 - 1)/( σ - σ 2).
Pages: 509–529
Keywords: keywords distance-regular graphs; primitive idempotents; cosine sequence; locally strongly regular; 1-homogeneous property; tight distance-regular graph; pseudo primitive idempotent; tight edges; pseudo 1-homogeneous
Full Text: PDF
References
1. Bannai, E., Ito, T.: Algebraic Combinatorics I: Association Schemes. Benjamin-Cummings, California (1984)
2. Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin, Heidelberg (1989)
3. Curtin, B., Nomura, K.: 1-homogeneous, pseudo-1-homogeneous, and 1-thin distance-regular graphs. J. Comb. Theory Ser. B 93, 279-302 (2005)
4. Go, J.T., Terwilliger, P.M.: Tight distance-regular graphs and the subconstituent algebra. Eur. J. Comb. 23, 793-816 (2002)
5. Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall, New York (1993)
6. Jurišić, A., Koolen, J.: A local approach to 1-homogeneous graphs. Des. Codes Cryptogr. 21, 127-147 (2000)
7. Jurišić, A., Koolen, J., Terwilliger, P.: Tight Distance-Regular Graphs. J. Algebr. Comb. 12, 163-197 (2000)
8. Pascasio, A.A.: Tight graphs and their primitive idempotents. J. Algebr. Comb. 10, 47-59 (1999)
9. Terwilliger, P.M.: The subconstituent algebra of a distance-regular graph; thin modules with endpoint one. Linear Algebra Appl. 356, 157-187 (2002)
10. Terwilliger, P.M.: An inequality involving the local eigenvalues of a distance-regular graph. J. Algebr.
2. Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin, Heidelberg (1989)
3. Curtin, B., Nomura, K.: 1-homogeneous, pseudo-1-homogeneous, and 1-thin distance-regular graphs. J. Comb. Theory Ser. B 93, 279-302 (2005)
4. Go, J.T., Terwilliger, P.M.: Tight distance-regular graphs and the subconstituent algebra. Eur. J. Comb. 23, 793-816 (2002)
5. Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall, New York (1993)
6. Jurišić, A., Koolen, J.: A local approach to 1-homogeneous graphs. Des. Codes Cryptogr. 21, 127-147 (2000)
7. Jurišić, A., Koolen, J., Terwilliger, P.: Tight Distance-Regular Graphs. J. Algebr. Comb. 12, 163-197 (2000)
8. Pascasio, A.A.: Tight graphs and their primitive idempotents. J. Algebr. Comb. 10, 47-59 (1999)
9. Terwilliger, P.M.: The subconstituent algebra of a distance-regular graph; thin modules with endpoint one. Linear Algebra Appl. 356, 157-187 (2002)
10. Terwilliger, P.M.: An inequality involving the local eigenvalues of a distance-regular graph. J. Algebr.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition