The local structure of a bipartite distance-regular graph. (English) Zbl 0940.05074

Summary: We consider a bipartite distance-regular graph \(\Gamma= (X,E)\) with diameter \(d\geq 3\). We investigate the local structure of \(\Gamma\), focusing on those vertices with distance at most 2 from a given vertex \(x\). To do this, we consider a subalgebra \({\mathcal R}={\mathcal R}(x)\) of \(\text{Mat}_{\widetilde X}(\mathbb{C})\), where \(\widetilde X\) denotes the set of vertices in \(X\) at distance \(2\) from \(x\). \({\mathcal R}\) is generated by matrices \(\widetilde A\), \(\widetilde J\), and \(\widetilde D\) defined as follows. For all \(y,z\in\widetilde X\), the \((y,z)\)-entry of \(\widetilde A\) is \(1\) if \(y\), \(z\) are at distance \(2\), and \(0\) otherwise. The \((y,z)\)-entry of \(\widetilde J\) equals \(1\), and the \((y,z)\)-entry of \(\widetilde D\) equals the number of vertices of \(X\) adjacent to each of \(x\), \(y\), and \(z\). We show that \({\mathcal R}\) is commutative and semisimple, with dimension at least \(2\). We assume that \(\dim{\mathcal R}\) is one of \(2\), \(3\), or \(4\), and explore the combinatorial implications of this. We are motivated by the fact that if \(\Gamma\) has a \(Q\)-polynomial structure, then \(\dim{\mathcal R}\leq 4\).


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


[1] Bannai, E.; Ito, T., Algebraic Combinatorics I, (1984), Benjamin-Cummings Menlo Park, CA · Zbl 0555.05019
[2] Biggs, N., Algebraic Graph Theory, (1974), Cambridge University Press Cambridge · Zbl 0284.05101
[3] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs, (1989), Springer New York · Zbl 0747.05073
[4] Caughman IV, J. S., The Terwilliger algebra for bipartite P- and Q-polynomial association schemes, Discrete Math., 196, 65-95, (1999) · Zbl 0924.05067
[5] Caughman IV, J. S., Spectra of bipartite P- and Q-polynomial association schemes, Graphs Comb., 14, 321-343, (1998) · Zbl 0917.05088
[6] Caughman IV, J. S., Intersection numbers of bipartite distance-regular graphs, Discrete Math., 163, 235-241, (1997) · Zbl 0883.05045
[7] Curtin, B., 2-homogeneous bipartite distance-regular graphs, Discrete Math., 187, 39-70, (1998) · Zbl 0958.05143
[8] B. Curtin, Bipartite distance-regular graphs, parts I and II, Graphs Comb. · Zbl 0939.05088
[9] Curtis, C. W.; Reiner, I., Representation Theory of Finite Groups and Associative Algebras, (1962), Interscience New York · Zbl 0131.25601
[10] van Dam, E. R., Regular graphs with four eigenvalues, Linear Algebra Appl., 226-228, 139-162, (1995) · Zbl 0839.05072
[11] van Dam, E. R., Three-class association schemes, J. Algebr. Comb., 10, 69-107, (1999) · Zbl 0929.05096
[12] van Dam, E. R.; Spence, E., Small regular graphs with four eigenvalues, Discrete Math., 189, 233-257, (1998) · Zbl 0956.05070
[13] Fiol, M. A., Some applications of the proper and adjacency polynomials in the theory of graph spectra, Electron. J. Comb., 4, #R21, (1997) · Zbl 0885.05084
[14] Godsil, C. D., Algebraic Combinatorics, (1993), Chapman & Hall, London · Zbl 0814.05075
[15] Nomura, K., Spin models on bipartite distance-regular graphs, J. Comb. Theory, Ser. B, 64, 300-313, (1995) · Zbl 0827.05060
[16] Terwilliger, P., The subconstituent algebra of an association scheme, J. Algebr. Comb., 1, 363-388, (1992) · Zbl 0785.05089
[17] 1993, 2, 73, 103
[18] 1993, 2, 177, 210
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.