×

zbMATH — the first resource for mathematics

A spectral version of the Moore problem for bipartite regular graphs. (English) Zbl 1428.05187
Summary: Let \(b(k,\theta)\) be the maximum order of a connected bipartite \(k\)-regular graph whose second largest eigenvalue is at most \(\theta\). In this paper, we obtain a general upper bound for \(b(k,\theta)\) for any \(0\leq \theta < 2 \sqrt{k-1}\). Our bound gives the exact value of \(b(k,\theta)\) whenever there exists a bipartite distance-regular graph of degree \(k\), second largest eigenvalue \(\theta\), diameter \(d\) and girth \(g\) such that \(g\geq 2d-2\). For certain values of \(d\), there are infinitely many such graphs of various valencies \(k\). However, for \(d = 11\) or \(d\geq 15\), we prove that there are no bipartite distance-regular graphs with \(g\geq 2d-2\).
MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C40 Connectivity
05C12 Distance in graphs
05C35 Extremal problems in graph theory
05E30 Association schemes, strongly regular graphs
42C05 Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis
90C05 Linear programming
94B65 Bounds on codes
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Abiad, Aida; Van Dam, Edwin R.; Fiol, Miquel Ángel, Some spectral and quasi-spectral characterizations of distance-regular graphs, J. Combin. Theory Ser. A, 143, 1-18 (2016) · Zbl 1342.05031
[2] Alon, Noga, Eigenvalues and expanders, Combinatorica, 6, 2, 83-96 (1986) · Zbl 0578.68051
[3] Alon, Noga; Milman, Vitali D., \( \lambda _1,\) isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, 38, 1, 73-88 (1985) · Zbl 0549.05051
[4] Bannai, Eiichi; Ito, Tatsuro, On the spectra of certain distance-regular graphs, J. Combin. Theory Ser. B, 27, 3, 274-293 (1979) · Zbl 0427.15005
[5] Bannai, Eiichi; Ito, Tatsuro, On the spectra of certain distance-regular graphs. II, Quart. J. Math. Oxford Ser. (2), 32, 4, 389-411 (1981) · Zbl 0475.05059
[6] Bannai, Eiichi; Ito, Tatsuro, Algebraic combinatorics. I: Association schemes, xxiv+425 p. pp. (1984), The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA · Zbl 0555.05019
[7] Brouwer, Andries E.; Cohen, Arjeh M.; Neumaier, Arnold, Distance-regular graphs, 18, xviii+495 p. pp. (1989), Springer-Verlag, Berlin · Zbl 0747.05073
[8] Brouwer, Andries E.; Haemers, Willem H., Spectra of graphs, xiv+250 p. pp. (2012), Springer, New York · Zbl 1231.05001
[9] Chung, Fan R. K., Diameters and eigenvalues, J. Amer. Math. Soc., 2, 2, 187-196 (1989) · Zbl 0678.05037
[10] Cioabă, Sebastian M.; Koolen, Jack H.; Nozaki, Hiroshi; Vermette, Jason R., Maximizing the order of a regular graph of given valency and second eigenvalue, SIAM J. Discrete Math., 30, 3, 1509-1525 (2016) · Zbl 1344.05086
[11] Cohn, Henry; Kumar, Abhinav, Universally optimal distribution of points on spheres, J. Amer. Math. Soc., 20, 1, 99-148 (2007) · Zbl 1198.52009
[12] Damerell, Robert Mark; Georgiacodis, Michael A., On the maximum diameter of a class of distance-regular graphs, Bull. London Math. Soc., 13, 4, 316-322 (1981) · Zbl 0457.05055
[13] Davidoff, Giuliana; Sarnak, Peter; Valette, Alain, Elementary number theory, group theory, and Ramanujan graphs, 55, x+144 p. pp. (2003), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 1032.11001
[14] Fuglister, Frederick J., On generalized Moore geometries. I, Discrete Math., 67, 3, 249-258 (1987) · Zbl 0626.51006
[15] Fuglister, Frederick J., On generalized Moore geometries. II, Discrete Math., 67, 3, 259-269 (1987) · Zbl 0626.51006
[16] Geronimus, James, On a set of polynomials, Ann. of Math. (2), 31, 4, 681-686 (1930) · JFM 56.0301.05
[17] Harris, Lawrence A., Lagrange polynomials, reproducing kernels and cubature in two dimensions, J. Approx. Theory, 195, 43-56 (2015) · Zbl 1314.41023
[18] Høholdt, Tom; Janwa, Heeralal, Eigenvalues and expansion of bipartite graphs, Des. Codes Cryptogr., 65, 3, 259-273 (2012) · Zbl 1254.05103
[19] Høholdt, Tom; Justesen, Jørn, On the sizes of expander graphs and minimum distances of graph codes, Discrete Math., 325, 38-46 (2014) · Zbl 1288.05070
[20] Hoory, Shlomo; Linial, Nathan; Wigderson, Avi, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.), 43, 4, 439-561 (2006) · Zbl 1147.68608
[21] Hora, Akihito; Obata, Nobuaki, Quantum probability and spectral analysis of graphs, xviii+371 p. pp. (2007), Springer: Springer, Berlin · Zbl 1141.81005
[22] Koledin, Tamara; Stanić, Zoran, Regular graphs with small second largest eigenvalue, Appl. Anal. Discrete Math., 7, 2, 235-249 (2013) · Zbl 1313.05229
[23] Koledin, Tamara; Stanić, Zoran, Reflexive bipartite regular graphs, Linear Algebra Appl., 442, 145-155 (2014) · Zbl 1282.05125
[24] Li, Wen-Ch’Ing Winnie; Solé, Patrick, Spectra of regular graphs and hypergraphs and orthogonal polynomials, European J. Combin., 17, 5, 461-477 (1996) · Zbl 0864.05072
[25] Marcus, Adam W.; Spielman, Daniel A.; Srivastava, Nikhil, Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. (2), 182, 1, 307-325 (2015) · Zbl 1316.05066
[26] Miller, Mirka; Sirán, Jozef, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin., 61 p. pp. (2005) · Zbl 1079.05043
[27] Nozaki, Hiroshi, Linear programming bounds for regular graphs, Graphs Combin., 31, 6, 1973-1984 (2015) · Zbl 1332.90160
[28] Singleton, Robert, On minimal graphs of maximum even girth, J. Combinatorial Theory, 1, 3, 306-332 (1966) · Zbl 0168.44703
[29] Teranishi, Yasuo; Yasuno, Fumiko, The second largest eigenvalues of regular bipartite graphs, Kyushu J. Math., 54, 1, 39-54 (2000) · Zbl 0990.05095
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.