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
Keywords: second eigenvalue, bipartite regular graph, bipartite distance-regular graph, expander, linear programming bound.
Cioabă, Sebastian M. 1; Koolen, Jack H. 2; Nozaki, Hiroshi 3
@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}, zbl = {1428.05187}, mrnumber = {4049844}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.71/} }
TY - JOUR AU - Cioabă, Sebastian M. AU - Koolen, Jack H. AU - Nozaki, Hiroshi TI - A spectral version of the Moore problem for bipartite regular graphs JO - Algebraic Combinatorics PY - 2019 SP - 1219 EP - 1238 VL - 2 IS - 6 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.71/ DO - 10.5802/alco.71 LA - en ID - ALCO_2019__2_6_1219_0 ER -
%0 Journal Article %A Cioabă, Sebastian M. %A Koolen, Jack H. %A Nozaki, Hiroshi %T A spectral version of the Moore problem for bipartite regular graphs %J Algebraic Combinatorics %D 2019 %P 1219-1238 %V 2 %N 6 %I MathOA foundation %U https://alco.centre-mersenne.org/articles/10.5802/alco.71/ %R 10.5802/alco.71 %G en %F ALCO_2019__2_6_1219_0
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 | DOI | MR | Zbl
[2] Eigenvalues and expanders, Combinatorica, Volume 6 (1986) no. 2, pp. 83-96 Theory of computing (Singer Island, Fla., 1984) | DOI | MR
[3] isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, Volume 38 (1985) no. 1, pp. 73-88 | DOI | MR
[4] On the spectra of certain distance-regular graphs, J. Combin. Theory Ser. B, Volume 27 (1979) no. 3, pp. 274-293 | DOI | MR | Zbl
[5] On the spectra of certain distance-regular graphs. II, Quart. J. Math. Oxford Ser. (2), Volume 32 (1981) no. 4, pp. 389-411 | DOI | MR | Zbl
[6] Algebraic combinatorics. I: Association schemes, Mathematics lecture note series, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984, xxiv+425 pages | MR | Zbl
[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 | DOI | MR | Zbl
[8] Spectra of graphs, Universitext, Springer, New York, 2012, xiv+250 pages | DOI | MR | Zbl
[9] Diameters and eigenvalues, J. Amer. Math. Soc., Volume 2 (1989) no. 2, pp. 187-196 | DOI | MR | Zbl
[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 | DOI | MR | Zbl
[11] Universally optimal distribution of points on spheres, J. Amer. Math. Soc., Volume 20 (2007) no. 1, pp. 99-148 | DOI | MR | Zbl
[12] On the maximum diameter of a class of distance-regular graphs, Bull. London Math. Soc., Volume 13 (1981) no. 4, pp. 316-322 | DOI | MR | Zbl
[13] Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, 55, Cambridge University Press, Cambridge, 2003, x+144 pages | DOI | MR | Zbl
[14] On generalized Moore geometries. I, Discrete Math., Volume 67 (1987) no. 3, pp. 249-258 | DOI | MR | Zbl
[15] On generalized Moore geometries. II, Discrete Math., Volume 67 (1987) no. 3, pp. 259-269 | DOI | MR | Zbl
[16] On a set of polynomials, Ann. of Math. (2), Volume 31 (1930) no. 4, pp. 681-686 | DOI | MR
[17] Lagrange polynomials, reproducing kernels and cubature in two dimensions, J. Approx. Theory, Volume 195 (2015), pp. 43-56 | DOI | MR | Zbl
[18] Eigenvalues and expansion of bipartite graphs, Des. Codes Cryptogr., Volume 65 (2012) no. 3, pp. 259-273 | DOI | MR | Zbl
[19] On the sizes of expander graphs and minimum distances of graph codes, Discrete Math., Volume 325 (2014), pp. 38-46 | DOI | MR | Zbl
[20] Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.), Volume 43 (2006) no. 4, pp. 439-561 | DOI | MR | Zbl
[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 | Zbl
[22] Regular graphs with small second largest eigenvalue, Appl. Anal. Discrete Math., Volume 7 (2013) no. 2, pp. 235-249 | DOI | MR | Zbl
[23] Reflexive bipartite regular graphs, Linear Algebra Appl., Volume 442 (2014), pp. 145-155 | DOI | MR | Zbl
[24] Spectra of regular graphs and hypergraphs and orthogonal polynomials, European J. Combin., Volume 17 (1996) no. 5, pp. 461-477 | DOI | MR | Zbl
[25] Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. (2), Volume 182 (2015) no. 1, pp. 307-325 | DOI | MR | Zbl
[26] Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. (2005), Paper no. DS14–Dec, 61 pages | Zbl
[27] Linear programming bounds for regular graphs, Graphs Combin., Volume 31 (2015) no. 6, pp. 1973-1984 | DOI | MR | Zbl
[28] On minimal graphs of maximum even girth, J. Combinatorial Theory, Volume 1 (1966) no. 3, pp. 306-332 | DOI | MR | Zbl
[29] The second largest eigenvalues of regular bipartite graphs, Kyushu J. Math., Volume 54 (2000) no. 1, pp. 39-54 | DOI | MR | Zbl
Cited by Sources: