Let be the maximum order of a connected bipartite -regular graph whose second largest eigenvalue is at most . In this paper, we obtain a general upper bound for for any . Our bound gives the exact value of whenever there exists a bipartite distance-regular graph of degree , second largest eigenvalue , diameter and girth such that . For certain values of , there are infinitely many such graphs of various valencies . However, for or , we prove that there are no bipartite distance-regular graphs with .
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.71
Classification: 05B25, 05C35, 05C50, 05E30, 42C05, 94B65
Keywords: second eigenvalue, bipartite regular graph, bipartite distance-regular graph, expander, linear programming bound.
Author's affiliations:
@article{ALCO_2019__2_6_1219_0, author = {Cioab\u{a}, Sebastian M. and Koolen, Jack H. and Nozaki, Hiroshi}, title = {A spectral version of the {Moore} problem for bipartite regular graphs}, journal = {Algebraic Combinatorics}, pages = {1219--1238}, publisher = {MathOA foundation}, volume = {2}, number = {6}, year = {2019}, doi = {10.5802/alco.71}, mrnumber = {4049844}, zbl = {1428.05187}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.71/} }
TY - JOUR TI - A spectral version of the Moore problem for bipartite regular graphs JO - Algebraic Combinatorics PY - 2019 DA - 2019/// SP - 1219 EP - 1238 VL - 2 IS - 6 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.71/ UR - https://www.ams.org/mathscinet-getitem?mr=4049844 UR - https://zbmath.org/?q=an%3A1428.05187 UR - https://doi.org/10.5802/alco.71 DO - 10.5802/alco.71 LA - en ID - ALCO_2019__2_6_1219_0 ER -
Cioabă, Sebastian M.; Koolen, Jack H.; Nozaki, Hiroshi. A spectral version of the Moore problem for bipartite regular graphs. Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 1219-1238. doi : 10.5802/alco.71. https://alco.centre-mersenne.org/articles/10.5802/alco.71/
[1] Some spectral and quasi-spectral characterizations of distance-regular graphs, J. Combin. Theory Ser. A, Volume 143 (2016), pp. 1-18 | Article | MR: 3519812 | Zbl: 1342.05031
[2] Eigenvalues and expanders, Combinatorica, Volume 6 (1986) no. 2, pp. 83-96 Theory of computing (Singer Island, Fla., 1984) | Article | MR: 875835
[3] isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, Volume 38 (1985) no. 1, pp. 73-88 | Article | MR: 782626
[4] On the spectra of certain distance-regular graphs, J. Combin. Theory Ser. B, Volume 27 (1979) no. 3, pp. 274-293 | Article | MR: 554295 | Zbl: 0427.15005
[5] On the spectra of certain distance-regular graphs. II, Quart. J. Math. Oxford Ser. (2), Volume 32 (1981) no. 4, pp. 389-411 | Article | MR: 635588 | Zbl: 0475.05059
[6] Algebraic combinatorics. I: Association schemes, Mathematics lecture note series, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984, xxiv+425 pages | MR: 882540 | Zbl: 0555.05019
[7] Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], 18, Springer-Verlag, Berlin, 1989, xviii+495 pages | Article | MR: 1002568 | Zbl: 0747.05073
[8] Spectra of graphs, Universitext, Springer, New York, 2012, xiv+250 pages | Article | MR: 2882891 | Zbl: 1231.05001
[9] Diameters and eigenvalues, J. Amer. Math. Soc., Volume 2 (1989) no. 2, pp. 187-196 | Article | MR: 965008 | Zbl: 0678.05037
[10] Maximizing the order of a regular graph of given valency and second eigenvalue, SIAM J. Discrete Math., Volume 30 (2016) no. 3, pp. 1509-1525 | Article | MR: 3537002 | Zbl: 1344.05086
[11] Universally optimal distribution of points on spheres, J. Amer. Math. Soc., Volume 20 (2007) no. 1, pp. 99-148 | Article | MR: 2257398 | Zbl: 1198.52009
[12] On the maximum diameter of a class of distance-regular graphs, Bull. London Math. Soc., Volume 13 (1981) no. 4, pp. 316-322 | Article | MR: 620044 | Zbl: 0457.05055
[13] Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, 55, Cambridge University Press, Cambridge, 2003, x+144 pages | Article | MR: 1989434 | Zbl: 1032.11001
[14] On generalized Moore geometries. I, Discrete Math., Volume 67 (1987) no. 3, pp. 249-258 | Article | MR: 915950 | Zbl: 0626.51006
[15] On generalized Moore geometries. II, Discrete Math., Volume 67 (1987) no. 3, pp. 259-269 | Article | MR: 915950 | Zbl: 0626.51006
[16] On a set of polynomials, Ann. of Math. (2), Volume 31 (1930) no. 4, pp. 681-686 | Article | MR: 1502972
[17] Lagrange polynomials, reproducing kernels and cubature in two dimensions, J. Approx. Theory, Volume 195 (2015), pp. 43-56 | Article | MR: 3339053 | Zbl: 1314.41023
[18] Eigenvalues and expansion of bipartite graphs, Des. Codes Cryptogr., Volume 65 (2012) no. 3, pp. 259-273 | Article | MR: 2988185 | Zbl: 1254.05103
[19] On the sizes of expander graphs and minimum distances of graph codes, Discrete Math., Volume 325 (2014), pp. 38-46 | Article | MR: 3181231 | Zbl: 1288.05070
[20] Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.), Volume 43 (2006) no. 4, pp. 439-561 | Article | MR: 2247919 | Zbl: 1147.68608
[21] Quantum probability and spectral analysis of graphs, Theoretical and Mathematical Physics, Springer, Berlin, 2007, xviii+371 pages (With a foreword by Luigi Accardi) | MR: 2316893 | Zbl: 1141.81005
[22] Regular graphs with small second largest eigenvalue, Appl. Anal. Discrete Math., Volume 7 (2013) no. 2, pp. 235-249 | Article | MR: 3135926 | Zbl: 1313.05229
[23] Reflexive bipartite regular graphs, Linear Algebra Appl., Volume 442 (2014), pp. 145-155 | Article | MR: 3134359 | Zbl: 1282.05125
[24] Spectra of regular graphs and hypergraphs and orthogonal polynomials, European J. Combin., Volume 17 (1996) no. 5, pp. 461-477 | Article | MR: 1397154 | Zbl: 0864.05072
[25] Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. (2), Volume 182 (2015) no. 1, pp. 307-325 | Article | MR: 3374962 | Zbl: 1316.05066
[26] Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. (2005), Paper no. DS14–Dec, 61 pages | Zbl: 1079.05043
[27] Linear programming bounds for regular graphs, Graphs Combin., Volume 31 (2015) no. 6, pp. 1973-1984 | Article | MR: 3417208 | Zbl: 1332.90160
[28] On minimal graphs of maximum even girth, J. Combinatorial Theory, Volume 1 (1966) no. 3, pp. 306-332 | Article | MR: 0201347 | Zbl: 0168.44703
[29] The second largest eigenvalues of regular bipartite graphs, Kyushu J. Math., Volume 54 (2000) no. 1, pp. 39-54 | Article | MR: 1762790 | Zbl: 0990.05095
Cited by Sources: