×

zbMATH — the first resource for mathematics

Linear programming bounds for regular graphs. (English) Zbl 1332.90160
Summary: P. Delsarte et al. [Geom. Dedicata 6, 363–388 (1977; Zbl 0376.05015)] used the linear programming method in order to find bounds for the size of spherical codes endowed with prescribed inner products between distinct points in the code. In this paper, we develop the linear programming method to obtain bounds for the number of vertices of connected regular graphs endowed with given distinct eigenvalues. This method is proved by some “dual” technique of the spherical case, motivated from the theory of association scheme. As an application of this bound, we prove that a connected \(k\)-regular graph satisfying \(g>2d-1\) has the minimum second-largest eigenvalue of all \(k\)-regular graphs of the same size, where \(d\) is the number of distinct non-trivial eigenvalues, and \(g\) is the girth. The known graphs satisfying \(g>2d-1\) are Moore graphs, incidence graphs of regular generalized polygons of order \((s,s)\), triangle-free strongly regular graphs, and the odd graph of degree 4.

MSC:
90C05 Linear programming
05D05 Extremal set theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Abiad, A., Van Dam, E.R., Fiol, M.A.: Some spectral and quasi-spectral characterizations of distance-regular graphs. arXiv:1404.3973 · Zbl 1342.05031
[2] Alon, N, Eigenvalues and expanders, Combinatorica, 6, 83-96, (1986) · Zbl 0661.05053
[3] Alon, N; Milman, VD, \(λ _1\), isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, 38, 73-88, (1985) · Zbl 0549.05051
[4] Bachoc, C, Linear programming bounds for codes in Grassmannian spaces, IEEE Trans. Inf. Theory, 52, 2111-2125, (2006) · Zbl 1282.94106
[5] Bachoc, C; Vallentin, F, Optimality and uniqueness of the \((4,10,1/6)\) spherical code, J. Combin. Theory Ser. A, 116, 195-204, (2009) · Zbl 1160.94018
[6] Bannai, E., Ito, T.: Algebraic Combinatorics I: Association Schemes. Benjamin/Cummings, Menlo Park (1984) · Zbl 0555.05019
[7] Bannai, E; Ito, T, On finite Moore graphs, J. Fac. Sci. Univ. Tokyo Ser. A, 20, 191-208, (1973) · Zbl 0275.05121
[8] Barg, A; Purkayastha, P, Bounds on ordered codes and orthogonal arrays, Mosc. Math. J., 9, 211-243, (2009) · Zbl 1220.05135
[9] Benson, CT, Minimal regular graphs of girths eight and twelve, Can. J. Math., 18, 1091-1094, (1966) · Zbl 0146.45701
[10] Brouwer, AE, The uniqueness of the strongly regular graph on \(77\) points, J. Graph Theory, 7, 455-461, (1983) · Zbl 0523.05021
[11] Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin (1989) · Zbl 0747.05073
[12] Brouwer, AE; Haemers, WH, The gewirtz graph: an exercise in the theory of graph spectra, Eur. J. Combin., 14, 397-407, (1993) · Zbl 0794.05076
[13] Cohen, AM; Tits, J, On generalized hexagons and a near octagon whose lines have three points, Eur. J. Combin., 6, 13-27, (1985) · Zbl 0565.05014
[14] Cohn, H; Kumar, A, Universally optimal distribution of points on spheres, J. Am. Math. Soc., 20, 99-184, (2007) · Zbl 1198.52009
[15] Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups, 3rd edn. Springer, New York (1999) · Zbl 0915.52003
[16] Damerell, RM, On Moore graphs, Camb. Philos. Soc., 74, 227-236, (1973) · Zbl 0262.05132
[17] Damerell, RM; Georgiacodis, MA, On the maximum diameter of a class of distance-regular graphs, Bull. Lond. Math. Soc., 13, 316-322, (1981) · Zbl 0457.05055
[18] Delsarte, P, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., 10, 1-97, (1973) · Zbl 1075.05606
[19] Delsarte, P; Goethals, JM; Seidel, JJ, Spherical codes and designs, Geom. Dedicata, 6, 363-388, (1977) · Zbl 0376.05015
[20] Dodziuk, J, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Am. Math. Soc., 284, 787-794, (1984) · Zbl 0512.39001
[21] Ericson, T., Zinoviev, V.: Codes on Euclidean Spheres. North-Holland Mathematical Library, 63, North-Holland Publishing Co., Amsterdam (2001) · Zbl 0985.94050
[22] Feit, W; Higman, G, The nonexistence of certain generalized polygons, J. Algebra, 1, 114-131, (1964) · Zbl 0126.05303
[23] Gewirtz, A, Graphs with maximal even girth, Can. J. Math., 21, 915-934, (1969) · Zbl 0181.51801
[24] Godsil, C.D.: Problems in algebraic combinatorics. Electron. J. Combin. 2 #F1, 20 (1995) · Zbl 0814.05075
[25] Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001) · Zbl 0968.05002
[26] Hall, M, Uniqueness of the projective plane with \(57\) points, Proc. Am. Math. Soc., 4, 912-916, (1953) · Zbl 0052.16503
[27] Hall, M; Swift, JD; Killgrove, R, On projective planes of order nine, Math. Tables Aids Comput., 13, 233-246, (1959) · Zbl 0094.33702
[28] Hall, M; Swift, JD; Walker, RJ, Uniqueness of the projective plane of order eight, Math. Tables Aids Comput., 10, 186-194, (1956) · Zbl 0073.36502
[29] Higman, DG; Sims, CC, A simple group of order 44,352,000, Math. Z., 105, 110-113, (1968) · Zbl 0186.04002
[30] Hoffman, AJ, On the polynomial of a graph, Am. Math. Mon., 70, 30-36, (1963) · Zbl 0112.14901
[31] Hoffman, AJ; Singleton, RR, On Moore graphs with diameters 2 and 3, IBM J. Res. Dev., 4, 497-504, (1960) · Zbl 0096.38102
[32] Hoory, S; Linial, N; Wigderson, A, Expander graphs and their applications, Bull. Am. Math. Soc., 43, 439-561, (2006) · Zbl 1147.68608
[33] Hora, A., Obata, N.: Quantum Probability and Spectral Analysis of Graphs. Theoretical and Mathematical Physics. Springer, Berlin (2007) · Zbl 1141.81005
[34] Kabatiansky, GA; Levenshtein, VI, Bounds for packings on a sphere and in space, Probl. Peredachi Inf., 14, 3-25, (1978) · Zbl 0407.52005
[35] Koledin, T; Stanić, Z, Regular graphs whose second largest eigenvalue is at most 1, Novi Sad J. Math., 43, 145-153, (2013) · Zbl 1299.05223
[36] Levenshtein, VI, Designs as maximum codes in polynomial metric spaces, Acta Appl. Math., 29, 1-82, (1992) · Zbl 0767.05097
[37] MacInnes, CR, Finite planes with less than eight points on a line, Am. Math. Mon., 14, 171-174, (1907) · JFM 38.0510.07
[38] Martin, WJ; Tanaka, H, Commutative association schemes, Eur. J. Combin., 30, 1497-1525, (2009) · Zbl 1228.05317
[39] Moon, A, Characterization of the odd graphs \(O_k\) by parameters, Discrete Math., 42, 91-97, (1982) · Zbl 0494.05035
[40] Musin, OR, The kissing number in four dimensions, Ann. Math., 168, 1-32, (2008) · Zbl 1169.52008
[41] Musin, OR; Tarasov, AS, The strong thirteen spheres problem, Discrete Comput. Geom., 48, 128-141, (2012) · Zbl 1269.52015
[42] Odlyzko, AM; Sloane, NJA, New bounds on the number of unit spheres that can touch a unit sphere in \(n\) dimensions, J. Combin. Theory Ser. A, 26, 210-214, (1979) · Zbl 0408.52007
[43] Payne, SE, All generalized quadrangles of order 3 are known, J. Combin. Theory Ser. A, 18, 203-206, (1975) · Zbl 0298.50017
[44] Payne, SE, Generalized quadrangles of order 4. I, J. Combin. Theory Ser. A, 22, 267-279, (1977) · Zbl 0353.05019
[45] Payne, SE, Generalized quadrangles of order 4. II, J. Combin. Theory Ser. A, 22, 280-288, (1977) · Zbl 0353.05019
[46] Scott, LL, A conditions on higman’s parameters, Not. Am. Math. Soc., 701, 20-45, (1973)
[47] Seidel, JJ, Strongly regular graphs with \((-1,1,0)\) adjacency matrix having eigenvalue \(3\), Linear Algebra Appl., 1, 281-298, (1968) · Zbl 0159.25403
[48] Singleton, R, On minimal graphs of maximum even girth, J. Combin. Theory, 1, 306-332, (1966) · Zbl 0168.44703
[49] Tarnanen, H, Upper bounds on permutation codes via linear programming, Eur. J. Combin., 20, 101-114, (1999) · Zbl 0915.94010
[50] Tutte, W.T.: Connectivity in Graphs. Toronto University Press, Toronto (1967) · Zbl 0146.45603
[51] Veblen, O; Maclagan-Wedderburn, JH, Non-Desarguesian and non-Pascalian geometries, Trans. Am. Math. Soc., 8, 379-388, (1907) · JFM 38.0502.01
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.