zbMATH — the first resource for mathematics

A new characterization of taut distance-regular graphs of odd diameter. (English) Zbl 1278.05251
Summary: We consider a bipartite distance-regular graph \(\varGamma\) with vertex set \(X\), diameter \(D\geq 4\), and valency \(k\geq 3\). Let \(\mathbb C^X\) denote the vector space over \(\mathbb C\) consisting of column vectors with rows indexed by \(X\) and entries in \(\mathbb C\). For \(z\in X\), let \(\hat{z}\) denote the vector in \(\mathbb C^X\) with a 1 in the \(z^{th}\) row and 0 in all other rows. For \(0\leq i\leq D\), let \(\varGamma_i(z)\) denote the set of vertices in \(X\) that are distance \(i\) from \(z\). Fix \(x,y\in X\) with distance \(\partial (x,y)=2\). For \(0\leq i,j\leq D\), we define \(w_{ij}=\sum\hat{z}\), where the sum is over all vertices \(z\in\varGamma_i(x)\cap\varGamma_j(y)\). Define a parameter \(\varDelta\) in terms of the intersection numbers by \(\varDelta=(b_1-1)(c_3-1)-(c_2-1)p^2_{22}\). For \(2\leq i\leq D-2\) we define vectors \(w_{ii}^+=\sum |\varGamma_1(x)\cap\varGamma_1(y)\cap\varGamma_{i-1}(z)|\hat{z}\), where the sum is over all vertices \(z\in\varGamma_i(x)\cap\varGamma_i(y)\). We define \(W=\mathrm{span}\{w_{ij},w_{hh}^+ \mid 0\leq i,j\leq D,2\leq h\leq D-2\}\). In [Discrete Math. 225, No. 1–3, 193–216 (2000; Zbl 1001.05124)], M. MacLean defined what it means for \(\varGamma\) to be taut. Assume \(D\) is odd. We show \(\varGamma\) is taut if and only if \(\varDelta\neq 0\) and the subspace \(W\) is invariant under multiplication by the adjacency matrix.

05E30 Association schemes, strongly regular graphs
05C12 Distance in graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI
[1] Bannai, E.; Ito, T., Algebraic combinatorics I: association schemes, (1984), Benjamin/Cummings London · Zbl 0555.05019
[2] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-regular graphs, (1989), Springer-Verlag Berlin · Zbl 0747.05073
[3] Caughman, J. S., The Terwilliger algebras of bipartite \(P\)- and \(Q\)-polynomial schemes, Discrete Math., 196, 65-95, (1999) · Zbl 0924.05067
[4] Curtin, B., 2-homogeneous bipartite distance-regular graphs, Discrete Math., 187, 39-70, (1998) · Zbl 0958.05143
[5] Curtin, B., Bipartite distance-regular graphs I, Graphs Combin., 15, 143-158, (1999) · Zbl 0927.05083
[6] Curtin, B., Bipartite distance-regular graphs II, Graphs Combin., 15, 377-391, (1999) · Zbl 0939.05088
[7] Curtis, C.; Reiner, I., Representation theory of finite groups and associative algebras, (1962), Interscience New York · Zbl 0131.25601
[8] Egge, E., A generalization of the Terwilliger algebra, J. Algebra, 233, 213-252, (2000) · Zbl 0960.05108
[9] Go, J. T., The Terwilliger algebra of the hypercube, European J. Combin., 23, 399-429, (2002) · Zbl 0997.05097
[10] Godsil, C. D., Algebraic combinatorics, (1993), Chapman and Hall, Inc. New York · Zbl 0814.05075
[11] Hobart, S. A.; Ito, T., The structure of nonthin irreducible \(T\)-modules: ladder bases and classical parameters, J. Algebraic Combin., 7, 53-75, (1998) · Zbl 0911.05059
[12] MacLean, M., An inequality involving two eigenvalues of a bipartite distance-regular graph, Discrete Math., 225, 193-216, (2000) · Zbl 1001.05124
[13] MacLean, M., Taut distance-regular graphs of odd diameter, J. Algebraic Combin., 17, 125-147, (2003) · Zbl 1014.05072
[14] MacLean, M., A new approach to the bipartite fundamental bound, Discrete Math., 312, 3195-3202, (2012) · Zbl 1254.05054
[15] MacLean, M.; Terwilliger, P., Taut distance-regular graphs and the subconstituent algebra, Discrete Math., 306, 1694-1721, (2006) · Zbl 1100.05104
[16] MacLean, M.; Terwilliger, P., The subconstituent algebra of a bipartite distance-regular graph: thin modules with endpoint two, Discrete Math., 308, 1230-1259, (2008) · Zbl 1136.05076
[17] Miklavič, S., On bipartite \(Q\)-polynomial distance-regular graphs, European J. Combin., 28, 94-110, (2007) · Zbl 1200.05262
[18] Nomura, K., Homogeneous graphs and regular near polygons, J. Combin. Theory Ser. B, 60, 63-71, (1994) · Zbl 0793.05130
[19] Terwilliger, P., The subconstituent algebra of an association scheme I, J. Algebraic Combin., 1, 363-388, (1992) · Zbl 0785.05089
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.