zbMATH — the first resource for mathematics

Taut distance-regular graphs of odd diameter. (English) Zbl 1014.05072
A distance-regular graph \(\Gamma\) with diameter \(D\geq 4\), valency \(k\geq 3\) and eigenvalues \(\theta_0>\cdots >\theta_D\) is considered. Let \(M\) denote the Bose-Mesner algebra of \(\Gamma\). For \(0\leq i\leq D\), let \(E_i\) denote the primitive idempotents of \(M\) associated with \(\theta_i\) (\(E_0\) and \(E_d\) are called trivial idempotents). A pair \(E,F\) of nontrivial primitive idempotents of \(M\) is taut whenever the entry-wise product \(E\circ F\) is a linear combination of two primitive idempotents of \(M\). The graph \(\Gamma\) is taut whenever \(\Gamma\) has at least one taut pair of primitive idempotents, but \(\Gamma\) is not 2-homogeneous in the sense of Nomura-Curtin.
In this paper the taut graphs of odd diameter \(D\) are investigated. Let \(E,F\) be nontrivial primitive idempotents of \(M\) and let \(\sigma_0,\dots ,\sigma_d\) and \(\rho_0,\dots ,\rho_d\) denote the cosine sequences of \(E\) and \(F\), respectively. The pair \(E,F\) is taut if and only if there exist real scalars \(\alpha\) and \(\beta\) such that \[ \sigma_{i+1}\rho_{i+1}-\sigma_{i-1}\rho_{i-1}= \alpha\sigma_i(\rho_{i+1}-\rho_{i-1})+\beta\rho_i(\sigma_{i+1}-\sigma_{i-1})\quad (1\leq i\leq D-1). \] If \(D\) is odd and the pair \(E,F\) is taut, then all intersection numbers of \(\Gamma\) are determined in terms of \(\sigma_1,\rho_1,\alpha,\beta\) (Theorem 5.8). As \(E_1,E_d\) is a taut pair in any taut graph for \(d=(D-1)/2\), all intersection numbers of taut graphs \(\Gamma\) are determined in terms of \(k,\mu,\theta_1,\theta_d\) (Corollary 5.9). If \(\Gamma\) is taut and \(D\) is odd, then \(\Gamma\) is an antipodal 2-cover (Theorem 6.4).

05E30 Association schemes, strongly regular graphs
Full Text: DOI
[1] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin/Cummings, London, 1984. · Zbl 0555.05019
[2] A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
[3] Curtin, B., 2-homogeneous bipartite distance-regular graphs, Discrete Math., 187, 39-70, (1998) · Zbl 0958.05143
[4] Dickie, G.; Terwilliger, P., Dual bipartite Q-polynomial distance-regular graphs, Europ.J.Combin., 17, 613-623, (1996) · Zbl 0921.05064
[5] C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
[6] A. Jurišić and J. Koolen, “1-homogeneous graphs with Cocktail Party µ-graphs,” J.Alg.Combin., in press.
[7] Jurišić, A.; Koolen, J., Krein parameters and antipodal tight graphs with diameter 3 and 4, Discrete Math., 244, 181-202, (2002) · Zbl 1024.05086
[8] Jurišić, A.; Koolen, J., Nonexistence of some antipodal distance-regular graphs of diameter four, Europ.J.Combin., 21, 1039-1046, (2000) · Zbl 0958.05139
[9] Jurišić, A.; Koolen, J., A local approach to 1-homogeneous graphs, Designs, Codes, and Cryptography, 21, 127-147, (2000) · Zbl 0964.05073
[10] Jurišić, A.; Koolen, J.; Terwilliger, P., No article title, Tight distance-regular graphs with small diameter, 36, 621, (1998)
[11] Jurišić, A.; Koolen, J.; Terwilliger, P., Tight distance-regular graphs, J.Alg.Combin., 12, 163-197, (2000) · Zbl 0959.05121
[12] MacLean, M., An inequality involving two eigenvalues of a bipartite distance-regular graph, Discrete Math., 225, 193-216, (2000) · Zbl 1001.05124
[13] Nomura, K., Homogeneous graphs and regular near polygons, J.Combin.Theory Ser.B, 60, 63-71, (1994) · Zbl 0793.05130
[14] Nomura, K., Spin models on bipartite distance-regular graphs, J.Combin.Theory Ser.B, 64, 300-313, (1995) · Zbl 0827.05060
[15] A.Pascasio, “An inequality in character algebras,” Discrete Math., in press. · Zbl 1014.05076
[16] Pascasio, A., An inequality on the cosines of a tight distance-regular graph, Linear Algebra Appl., 325, 147-159, (2001) · Zbl 0979.05112
[17] Pascasio, A., Tight distance-regular graphs and the Q-polynomial property, Graphs Combin., 17, 149-169, (2001) · Zbl 0993.05147
[18] Pascasio, A., Tight graphs and their primitive idempotents, J.Alg.Combin., 10, 47-59, (1999) · Zbl 0927.05085
[19] Tomiyama, M., A note on the primitive idempotents of distance-regular graphs, Discrete Math., 240, 281-294, (2001) · Zbl 0993.05148
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.