×

zbMATH — the first resource for mathematics

2-homogeneous bipartite distance-regular graphs. (English) Zbl 0958.05143
Summary: Let \(\Gamma\) denote a bipartite distance-regular graph with diameter \(D\geq 3\) and valency \(k\geq 3\). \(\Gamma\) is said to be 2-homogeneous whenever for all integers \(i\) \((1\leq i\leq D-1)\) and for all vertices \(x\), \(y\), \(z\) at distance \(\partial(x, y)= 2\), \(\partial(x,z)= i\), \(\partial(y,z)= i\), the number \(\gamma_i\) of vertices adjacent to both \(x\) and \(y\) and at distance \(i-1\) from \(z\) is a constant depending only upon \(i\).
We characterize the 2-homogeneous property in three ways. These characterizations involve the intersection numbers, the eigenvalues, and the Krein parameters, respectively.
First, we obtain a sequence of inequalities involving the intersection numbers of \(\Gamma\). We show that equality is attained in every case if and only if \(\Gamma\) is 2-homogeneous. Second, we obtain a number of inequalities involving the eigenvalues of \(\Gamma\). We show that equality is attained in any one of them if and only if equality is attained in all of them if and only if \(\Gamma\) is 2-homogeneous. Third, we show that the following are equivalent: (i) \(\Gamma\) is 2-homogeneous; (ii) \(\Gamma\) is an antipodal 2-cover and Q-polynomial; and (iii) \(\Gamma\) has a Q-polynomial structure for which the Krein parameters \(q^i_{1i}= 0\) \((0\leq i\leq D)\).

MSC:
05E30 Association schemes, strongly regular graphs
05C12 Distance in graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bannai, E.; Ito, T., Algebraic combinatorics I: association schemes, (1984), The Benjamin/Cummings Publishing Company, Inc. Menlo Park · Zbl 0555.05019
[2] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer New York · Zbl 0747.05073
[3] Caughman, S., Intersection numbers of bipartite distance-regular graphs, Discrete math., 163, 235-241, (1997) · Zbl 0883.05045
[4] S. Caughman, IV, Spectra of bipartite P- and Q-polynomial association schemes, Graphs Combin., to appear. · Zbl 0917.05088
[5] B. Curtin, Bipartite distance-regular graphs, Part I, Graphs Combin., to appear. · Zbl 0927.05083
[6] B. Curtin, Bipartite distance-regular graphs, Part II, Graphs Combin., to appear. · Zbl 0939.05088
[7] G.A. Dickie, Almost dual imprimitive distance-regular graphs, European J. Combin., to appear.
[8] G.A. Dickie, A note on Q-polynomial association schemes, J. Algebraic Combin., to appear. · Zbl 0898.05084
[9] Dickie, G.A.; Terwilliger, P.M., Dual bipartite Q-polynomial distance-regular graphs, European J. combin., 17, 613-624, (1996) · Zbl 0921.05064
[10] Godsil, C.D., Algebraic combinatorics, (1993), Chapman & Hall New York · Zbl 0814.05075
[11] Nomura, K., Homogeneous graphs and regular near polygons, J. combin. theory ser. B, 60, 63-71, (1994) · Zbl 0793.05130
[12] Nomura, K., Spin models on bipartite distance-regular graphs, J. combin. theory ser. B, 64, 2, 300-313, (1994) · Zbl 0827.05060
[13] Nomura, K., Spin models on triangle-free connected graphs, J. combin. theory ser. B, 67, 284-295, (1996) · Zbl 0857.05095
[14] Nomura, K., Spin models and almost bipartite 2-homogeneous graphs, Adv. stud. pure math., 24, 285-308, (1996) · Zbl 0858.05101
[15] Terwilliger, P., Balanced sets and Q-polynomial association schemes, Graphs combin., 4, 87-94, (1988) · Zbl 0644.05016
[16] Terwilliger, P., The subconstituent algebra of an association scheme, part I, J. algebraic combin., 1, 4, 363-388, (1992) · Zbl 0785.05089
[17] Terwilliger, P., The subconstituent algebra of an association scheme, part II, J. algebraic combin., 2, 1, 73-103, (1993) · Zbl 0785.05090
[18] Terwilliger, P., The subconstituent algebra of an association scheme, part III, J. algebraic combin., 2, 2, 177-210, (1993) · Zbl 0785.05091
[19] Terwilliger, P., A new inequality for distance-regular graphs, Discrete math., 137, 319-332, (1995) · Zbl 0814.05074
[20] Yamazaki, N., Bipartite distance-regular graphs with an eigenvalue of multiplicity k, J. combin. 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.