Pseudo 1-homogeneous distance-regular graphs. (English) Zbl 1160.05060

Jurišić, Aleksandar; Terwilliger, Paul

J. Algebr. Comb. 28, No. 4, 509-529 (2008).

Summary: Let \(\Gamma \) be a distance-regular graph of diameter \(d\geq 2\) and \(a_{1} \neq 0\). Let \(\theta \) be a real number. A pseudo cosine sequence for \(\theta \) is a sequence of real numbers \(\sigma_{0},\dots ,\sigma_{d}\) such that \(\sigma_{0}=1\) and \(c_{i} \sigma_{i - 1}+a_{i} \sigma_{i}+b_{i} \sigma_{i+1}=\theta \sigma_{i}\) for all \(i\in \{0,\dots ,d - 1\}\). Furthermore, a pseudo primitive idempotent for \(\theta \) is \(E_{\theta }=s \sum_{i=0}^ d \sigma_{i} A_{i}\), where \(s\) is any nonzero scalar. Let \(\hat{v}\) be the characteristic vector of a vertex \(v\in V\Gamma \). For an edge \(xy\) of \(\Gamma \) 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 \(\theta \) whenever \(\theta \neq k\) and a nontrivial linear combination of vectors \(E\hat{x} , E\hat{y}\) and \(Ew\) is contained in \(\mathrm{Span}\{\hat{z}\mid z\in V{\Gamma},\;\partial(z,x)=d=\partial(z,y)\}\). When an edge of \(\Gamma \) is tight with respect to two distinct real numbers, a parameterization with \(d+1\) parameters of the members of the intersection array of \(\Gamma \) is given (using the pseudo cosines \(\sigma_{1},\dots ,\sigma_{d}\), and an auxiliary parameter \(\varepsilon \)).
Let \(S\) be the set of all the vertices of \(\Gamma \) that are not at distance \(d\) from both vertices \(x\) and \(y\) that are adjacent. The graph \(\Gamma \) 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 \(\Gamma \) 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 \(\Gamma \). Then the graph \(\Gamma \) 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 \(\sigma _{1},\dots ,\sigma_{d },\varepsilon \) and the local graph of \(x\) is strongly regular with nontrivial eigenvalues \(a_{1} \sigma /(1+\sigma )\) and \((\sigma_{2} - 1)/(\sigma - \sigma_{2})\).

MSC:

05E30	Association schemes, strongly regular graphs
05C12	Distance in graphs

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

References:

[1]	Bannai, E., Ito, T.: Algebraic Combinatorics I: Association Schemes. Benjamin-Cummings, California (1984) · Zbl 0555.05019
[2]	Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin, Heidelberg (1989) · Zbl 0747.05073
[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) · Zbl 1060.05101
[4]	Go, J. T.; Terwilliger, P. M., Tight distance-regular graphs and the subconstituent algebra, Eur. J. Comb., 23, 793-816, (2002) · Zbl 1014.05070
[5]	Godsil, C.D.: Algebraic Combinatorics. Chapman and Hall, New York (1993) · Zbl 0784.05001
[6]	Jurišić, A.; Koolen, J., A local approach to 1-homogeneous graphs, Des. Codes Cryptogr., 21, 127-147, (2000) · Zbl 0964.05073
[7]	Jurišić, A.; Koolen, J.; Terwilliger, P., Tight Distance-Regular Graphs, J. Algebr. Comb., 12, 163-197, (2000) · Zbl 0959.05121
[8]	Pascasio, A. A., Tight graphs and their primitive idempotents, J. Algebr. Comb., 10, 47-59, (1999) · Zbl 0927.05085
[9]	Terwilliger, P. M., The subconstituent algebra of a distance-regular graph; thin modules with endpoint one, Linear Algebra Appl., 356, 157-187, (2002) · Zbl 1011.05066
[10]	Terwilliger, P. M., An inequality involving the local eigenvalues of a distance-regular graph, J. Algebr. Comb., 19, 143-172, (2004) · Zbl 1047.05045
[11]	Terwilliger, P. M.; Weng, C., Distance-regular graphs, pseudo primitive idempotents, and the Terwilliger algebra, Eur. J. Comb., 25, 287-298, (2004) · Zbl 1035.05104