Algebraic characterizations of regularity properties in bipartite graphs. (English) Zbl 1292.05273

Eur. J. Comb. 34, No. 8, 1223-1231 (2013); corrigendum ibid. 38, 130-132 (2014).
Summary: Regular and distance-regular characterizations of general graphs are well-known. In particular, the spectral excess theorem states that a connected graph \(\Gamma\) is distance-regular if and only if its spectral excess (a number that can be computed from the spectrum) equals the average excess (the mean of the numbers of vertices at extremal distance from every vertex). The aim of this paper is to derive new characterizations of regularity and distance-regularity for the more restricted family of bipartite graphs. In this case, some characterizations of (bi)regular bipartite graphs are given in terms of the mean degrees in every partite set and the Hoffman polynomial. Moreover, it is shown that the conditions for having distance-regularity in such graphs can be relaxed when compared with general graphs. Finally, a new version of the spectral excess theorem for bipartite graphs is presented.


05E30 Association schemes, strongly regular graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI arXiv


[1] Bannai, E.; Ito, T., Algebraic combinatorics I: association schemes, (1984), Benjamin/Cummings Menlo Park CA · Zbl 0555.05019
[2] R.A. Beezer, Distance polynomial graphs, in: Proc. Sixth Caribbean Conf. on Combin. and Computing, Trinidad, 1991, pp. 51-73.
[3] Biggs, N., Algebraic graph theory, (1993), Cambridge University Press Cambridge
[4] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-regular graphs, (1989), Springer-Verlag Berlin, New York · Zbl 0747.05073
[5] Brouwer, A. E.; Haemers, W. H., Spectra of graphs, (2012), Springer-Verlag Berlin, New York, Available online at http://homepages.cwi.nl/ aeb/math/ipm/ · Zbl 0794.05076
[6] Cámara, M.; Fàbrega, J.; Fiol, M. A.; Garriga, E., Some families of orthogonal polynomials of a discrete variable and their applications to graphs and codes, Electron. J. Combin., 16, 1, #R83, (2009) · Zbl 1230.05120
[7] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of graphs, theory and application, (1982), VEB Deutscher Verlag der Wissenschaften Berlin
[8] Dalfó, C.; Fiol, M. A.; Garriga, E., On \(k\)-walk-regular graphs, Electron. J. Combin., 16, 1, #R47, (2009) · Zbl 1226.05107
[9] Dalfó, C.; van Dam, E. R.; Fiol, M. A.; Garriga, E., Dual concepts of almost distance-regularity and the spectral excess theorem, Discrete Math., (2012) · Zbl 1245.05032
[10] Dalfó, C.; van Dam, E. R.; Fiol, M. A.; Garriga, E.; Gorissen, B. L., On almost distance-regular graphs, J. Combin. Theory Ser. A, 118, 1094-1113, (2011) · Zbl 1225.05249
[11] Fiol, M. A., Algebraic characterizations of distance-regular graphs, Discrete Math., 246, 111-129, (2002) · Zbl 1025.05060
[12] Fiol, M. A., On pseudo-distance-regularity, Linear Algebra Appl., 323, 145-165, (2001) · Zbl 0978.05050
[13] Fiol, M. A.; Gago, S.; Garriga, E., A simple proof of the spectral excess theorem for distance-regular graphs, Linear Algebra Appl., 432, 2418-2422, (2010) · Zbl 1221.05112
[14] Fiol, M. A.; Garriga, E., From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B, 71, 162-183, (1997) · Zbl 0888.05056
[15] Fiol, M. A.; Garriga, E.; Yebra, J. L.A., Boundary graphs: the limit case of a spectral property, Discrete Math., 226, 155-173, (2001) · Zbl 0965.05068
[16] Fiol, M. A.; Garriga, E.; Yebra, J. L.A., Locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B, 68, 179-205, (1996) · Zbl 0861.05064
[17] Godsil, C. D., Algebraic combinatorics, (1993), Chapman and Hall New York · Zbl 0814.05075
[18] Godsil, C. D.; McKay, B. D., Feasibility conditions for the existence of walk-regular graphs, Linear Algebra Appl., 30, 51-61, (1980) · Zbl 0452.05045
[19] Godsil, C. D.; Royle, G., (Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, (2001), Springer-Verlag New York)
[20] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226-228, 593-616, (1995) · Zbl 0831.05044
[21] Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36, (1963) · Zbl 0112.14901
[22] Rowlinson, P., Linear algebra, (Beineke, L. W.; Wilson, R. J., Graph Connections, Oxford Lecture Ser. Math. Appl., vol. 5, (1997), Oxford Univ. Press New York), 86-99 · Zbl 0878.05059
[23] van Dam, E. R., The spectral excess theorem for distance-regular graphs: a global (over)view, Electron. J. Combin., 15, 1, #R129, (2008) · Zbl 1180.05130
[24] van Dam, E. R., Regular graphs with four eigenvalues, Linear Algebra Appl., 226-228, 139-162, (1995) · Zbl 0839.05072
[25] E.R. van Dam, J.H. Koolen, H. Tanaka, Distance-regular graphs, Manuscript, 2012. Available online at http://lyrawww.uvt.nl/ evandam/files/drg.pdf. · Zbl 1335.05062
[26] van Dam, E. R.; Spence, E., Combinatorial designs with two singular values II, partial geometric designs, Linear Algebra Appl., 396, 303-316, (2005) · Zbl 1055.05020
[27] Weichsel, P. M., On distance-regularity in graphs, J. Combin. Theory Ser. B, 32, 156-161, (1982) · Zbl 0477.05047
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.