# zbMATH — the first resource for mathematics

Maximizing the order of a regular graph of given valency and second eigenvalue. (English) Zbl 1344.05086

##### MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C35 Extremal problems in graph theory 68R10 Graph theory (including graph drawing) in computer science 90C05 Linear programming 90C35 Programming involving graphs or networks
##### Keywords:
second eigenvalue; regular graph; expander
Full Text:
##### References:
 [1] N. Alon, Eigenvalues and expanders, Combinatorica, 6 (1986), pp. 83–96. · Zbl 0661.05053 [2] A. Amit, S. Hoory, and N. Linial, A continuous analogue of the girth problem, J. Combin. Theory Ser. B, 84 (2002), pp. 340–363. · Zbl 1025.05041 [3] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin/Cummings, Menlo Park, CA, 1984. · Zbl 0555.05019 [4] C.T. Benson, Minimal regular graphs of girths eight and twelve, Canad. J. Math., 18 (1966), pp. 1091–1094. · Zbl 0146.45701 [5] A.E. Brouwer, The uniqueness of the strongly regular graph on 77 points, J. Graph Theory, 7 (1983), pp. 455–461. · Zbl 0523.05021 [6] A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer, New York, 1989. · Zbl 0747.05073 [7] A.E. Brouwer and W.H. Haemers, The Gewirtz graph: An exercise in the theory of graph spectra, European J. Combin., 14 (1993), pp. 397–407. · Zbl 0794.05076 [8] A.E. Brouwer and W.H. Haemers, Spectra of Graphs, Springer, New York, 2012. · Zbl 1231.05001 [9] F.C. Bussemaker, D.H. Cvetković, and J.J. Seidel, Graphs Related to Exceptional Root Systems, Report TH Eindhoven 76-WSK-05, 1976. · Zbl 0338.05116 [10] P.J. Cameron, J.M. Goethals, J.J. Seidel, and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra, 43 (1976), pp. 305–327. · Zbl 0337.05142 [11] S.M. Cioabă, On the extreme eigenvalues of regular graphs, J. Combin. Theory Ser. B, 96 (2006), pp. 367–373. [12] H. Cohn and A. Kumar, Universally optimal distribution of points on spheres, J. Amer. Math. Soc., 20 (2007), pp. 99–184. · Zbl 1198.52009 [13] R.M. Damerell and M.A. Georgiacodis, On the maximum diameter of a class of distance-regular graphs, Bull. Lond. Math. Soc., 13 (1981), pp. 316–322. · Zbl 0457.05055 [14] P.G. Doyle, A 27-Vertex Graph that is Vertex-Transitive and Edge-Transitive but not l-Transitive, http://arxiv.org/abs/math/0703861. [15] J. Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Math. J., 69 (1993), pp. 487–525. · Zbl 0785.05066 [16] A. Gewirtz, Graphs with maximal even girth, Canad. J. Math., 21 (1969), pp. 915–934. · Zbl 0181.51801 [17] C. Godsil and G. Royle, Algebraic Graph Theory, Grad. Texts in Math. 207, Springer, New York, 2001. · Zbl 0968.05002 [18] K. Guo and B. Mohar, Large regular bipartite graphs with median eigenvalue 1, Linear Algebra Appl., 449 (2014), pp. 68–75. · Zbl 1286.05087 [19] D.G. Higman and C.C. Sims, A simple group of order 44,352,000, Math. Z., 105 (1968), pp. 110–113. · Zbl 0186.04002 [20] A.J. Hoffman and R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. Res. Develop., 4 (1960), pp. 497–504. · Zbl 0096.38102 [21] T. Høholdt and J. Justesen, On the sizes of expander graphs and minimum distances of graph codes, Discrete Math., 325 (2014), pp. 38–46. · Zbl 1288.05070 [22] D. Holt, A graph which is edge transitive but not arc transitive, J. Graph Theory, 5 (1985), pp. 201–204. · Zbl 0423.05020 [23] S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc., 46 (2006), pp. 439–561. · Zbl 1147.68608 [24] M. Krivelevich and B. Sudakov, Pseudo-random graphs. More sets, graphs and numbers, in Proceedings of the Conference on Finite and Infinte Sets, Bolyai Soc. Math. Stud. 15, Springer, New York, 2006, pp. 199–262. · Zbl 1098.05075 [25] T. Koledin and Z. Staníc, Regular graphs whose second largest eigenvalue is at most $$1$$, Novi Sad J. Math., 43 (2013), pp. 145–153. · Zbl 1299.05223 [26] T. Koledin and Z. Staníc, Regular graphs with small second largest eigenvalue, Appl. Anal. Discrete Math., 7 (2013), pp. 235–249. · Zbl 1313.05229 [27] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica, 8 (1988), pp. 261–277. · Zbl 0661.05035 [28] A. Marcus, D.A. Spielman, and N. Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math., 182 (2015), pp. 307–325. · Zbl 1316.05066 [29] W.F. McGee, A minimal cubic graph of girth seven, Canad. Math. Bull., 3 (1960), pp. 149–152. · Zbl 0091.37504 [30] B. Mohar, A strengthening and a multipartite generalization of the Alon–Boppana–Serre theorem, Proc. Amer. Math. Soc., 138 (2010), pp. 3899–3909. · Zbl 1209.05147 [31] B. Mohar, Median eigenvalues of bipartite planar graphs, MATCH Commun. Math. Comput. Chem., 70 (2013), pp. 79–84. · Zbl 1299.05229 [32] B. Mohar and B. Tayfeh-Rezaie, Median eigenvalues of bipartite graphs, J. Algebraic Combin., 41 (2015), pp. 899–909. · Zbl 1317.05112 [33] A. Moon, Characterization of the odd graphs $$O_k$$ by parameters, Discrete Math., 42 (1982), pp. 91–97. · Zbl 0494.05035 [34] A. Nilli, On the second eigenvalue of a graph, Discrete Math., 91 (1991), pp. 207–210. · Zbl 0771.05064 [35] A. Nilli, Tight estimates for eigenvalues of regular graphs, Electron. J. Combin., 11 (2004), 9. · Zbl 1053.05082 [36] H. Nozaki, Linear Programming Bounds for Regular Graphs, Graphs Combin., 31 (2015), pp. 1973–1984. · Zbl 1332.90160 [37] O. Reingold, S. Vadhan, and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. of Math. (2), 155 (2002), pp. 157–187. · Zbl 1008.05101 [38] J.J. Seidel, Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3, Linear Algebra Appl., 1 (1968), pp. 281–298. · Zbl 0159.25403 [39] R. Singleton, On minimal graphs of maximum even girth, J. Combin. Theory, 1 (1966), pp. 306–332. · Zbl 0168.44703 [40] J.-P. Serre, Asymptotic distribution of the eigenvalues of the Hecke operator $$T_p$$, J. Amer. Math. Soc., 10 (1997), pp. 75–102. [41] Z. Staníc, On regular graphs and coronas whose second largest eigenvalue does not exceed $$1$$, Linear Multilinear Algebra, 58 (2010), pp. 545–554. [42] Y. Teranishi and F. Yasuno, The second largest eigenvalues of regular bipartite graphs, Kyushu J. Math., 54 (2000), pp. 39–54. · Zbl 0990.05095 [43] W.T. Tutte, A family of cubical graphs, Proc. Cambridge Phil. Soc., 43 (1947), pp. 459–474. · Zbl 0029.42401 [44] W.T. Tutte, Connectivity in Graphs, University of Toronto Press, Toronto, 1966. · Zbl 0146.45603 [45] J. Richey, N. Shutty, and M. Stover, Finiteness Theorems in Spectral Graph Theory, arXiv:1306.6548. [46] H. Yu, On the limit points of the smallest eigenvalues of regular graphs, Des. Codes Cryptogr., 65 (2012), pp. 77–88. · Zbl 1245.05090
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.