Almost 2-homogeneous bipartite distance-regular graphs. (English) Zbl 1002.05069

Summary: Let \(\Gamma= (X,R)\) denote a bipartite distance-regular graph with diameter \(d\geq 4\), and fix a vertex \(x\) of \(\Gamma\). The Terwilliger algebra of \(\Gamma\) with respect to \(x\) is the subalgebra \(T\) of \(\text{Mat}_X(\mathbb{C})\) generated by \(A\), \(E^*_0, E^*_1,\dots, E^*_d\), where \(A\) is the adjacency matrix of \(\Gamma\), and where \(E^*_i\) denotes the projection onto the \(i\)th subconstituent of \(\Gamma\) with respect to \(x\). Let \(W\) denote an irreducible \(T\)-module. \(W\) is said to be thin whenever \(\dim E^*_i W\leq 1\) \((0\leq i\leq d)\). The endpoint of \(W\) is \(\min\{i\mid E^*_i W\neq 0\}\). It is known that a thin irreducible \(T\)-module of endpoint 2 has dimension \(d-3\), \(d-2\), or \(d-1\).
\(\Gamma\) is said to be \(2\)-homogeneous whenever for all \(i\) \((1\leq i\leq d-1)\) and for all \(x,y,z\in X\) with \(\partial(x, y)= 2\), \(\partial(x, z)= i\), \(\partial(y, z)= i\), the number \(|\Gamma_1(x)\cap \Gamma_1(y)\cap \Gamma_{i- 1}(z)|\) is independent of \(x\), \(y\), \(z\). Nomura has classified the \(2\)-homogeneous bipartite distance-regular graphs. In this paper we study a slightly weaker condition. \(\Gamma\) is said to be almost \(2\)-homogeneous whenever for all \(i\) \((1\leq i\leq d-2)\) and for all \(x,y,z\in X\) with \(\partial(x, y)= 2\), \(\partial(x, z)= i\), \(\partial(y, z)= i\), the number \(|\Gamma_1(x)\cap \Gamma_1(y)\cap \Gamma_{i- 1}(z)|\) is independent of \(x\), \(y\), \(z\). We prove that the following are equivalent: (i) \(\Gamma\) is almost \(2\)-homogeneous; (ii) \(\Gamma\) has, up to isomorphism, a unique irreducible \(T\)-module of endpoint \(2\) and this module is thin. Moreover, \(\Gamma\) is \(2\)-homogeneous if and only if (i) and (ii) hold and the unique irreducible \(T\)-module of endpoint \(2\) has dimension \(d- 3\).


05E30 Association schemes, strongly regular graphs
05C12 Distance in graphs
Full Text: DOI


[1] Bannai, E.; Ito, T., Algebraic combinatorics I, (1984), Benjamin/Cummings Menlo Park · Zbl 0555.05019
[2] Brouwer, A.E., The uniqueness of a certain thin near octagon (or partial 2-geometry, or parallelism) derived from the binary golay code, IEEE trans. inform. theory, IT-29, 370-371, (1983) · Zbl 0505.94014
[3] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer New York · Zbl 0747.05073
[4] Cameron, P.J.; Goethals, J.M.; Seidel, J.J., Strongly regular graphs having strongly regular subconstituents, J. algebra, 55, 257-280, (1978) · Zbl 0444.05045
[5] Cameron, P.J.; van Lint, J.H., Graph theory, coding theory and block designs, (1975), Cambridge University Press Cambridge · Zbl 0314.94008
[6] Caughman, IV, J.S., The Terwilliger algebras of bipartite P- and Q-polynomial schemes, Discrete math., 196, 65-95, (1999) · Zbl 0924.05067
[7] Caughman, IV, J.S., Bipartite Q-polynomial quotients of antipodal distance-regular graphs, J. comb. theory, ser. B, 76, 291-296, (1999) · Zbl 0938.05064
[8] Collins, B.V.C., The girth of a thin distance-regular graph, Graphs comb., 13, 21-34, (1997)
[9] Curtin, B., 2-homogeneous bipartite distance-regular graphs, Discrete math., 187, 39-70, (1998) · Zbl 0958.05143
[10] Curtin, B., Bipartite distance-regular graphs, parts I and II, Graphs comb., 15, 143-158, 377-391, (1999) · Zbl 0939.05088
[11] Curtin, B., The local structure of a bipartite distance-regular graph, Europ. J. combinatorics, 20, 734-758, (1999) · Zbl 0940.05074
[12] B. Curtin, The Terwilliger algebra of a 2-homogeneous bipartite distance-regular graph (submitted.) · Zbl 1023.05139
[13] B. Curtin, K. Nomura, Distance-regular graphs related to the quantum enveloping algebra of sl(2), J. Algebr. Comb. (to appear.) · Zbl 0967.05067
[14] J. Go
[15] de la Harpe, P., Spin models for link polynomials, strongly regular graphs and jaeger’s higman – sims model, Pac. J. math., 162, 57-96, (1994) · Zbl 0795.57002
[16] Jaeger, F., Strongly regular graphs and spin models for the kauffman polynomial, Geom. ded., 44, 23-52, (1992) · Zbl 0773.57005
[17] Leonard, D.A., Orthogonal polynomials, duality and association schemes, SIAM J. math. anal., 13, 656-663, (1982) · Zbl 0495.33006
[18] Nomura, K., Distance-regular graphs of Hamming type, J. comb. theory, ser. B, 50, 160-167, (1990) · Zbl 0719.05070
[19] Nomura, K., Homogeneous graphs and regular near polygons, J. comb. theory, ser. B, 60, 63-71, (1994) · Zbl 0793.05130
[20] Nomura, K., Spin models on bipartite distance-regular graphs, J. comb. theory, ser. B, 64, 300-313, (1995) · Zbl 0827.05060
[21] Rifà, J.; Huguet, L., Classification of a class of distance-regular graphs via completely regular codes, Discrete appl. math., 26, 289-300, (1990) · Zbl 0687.05015
[22] Terwilliger, P., The subconstituent algebra of an association scheme, J. algebr. comb. 2 (1993), 73-103; 2 (1993), 177-210., 1, 363-388, (1992) · Zbl 0785.05089
[23] Yamazaki, N., Bipartite distance-regular graphs with an eigenvalue of multiplicity k, J. comb. theory, ser. B, 66, 34-37, (1995) · Zbl 0835.05087
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.