Geodesic
Some Observations on the Smallest Adjacency Eigenvalue of a Graph
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 467-493.

Voir la notice de l'article provenant de la source Library of Science

In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds.
Keywords: graph spectrum, smallest eigenvalue, adjacency matrix, graph decomposition, clique partition, claw-free graphs, maximum cut 
@article{DMGT_2020_40_2_a7,
     author = {Cioab\u{a}, Sebastian M. and Elzinga, Randall J. and Gregory, David A.},
     title = {Some {Observations} on the {Smallest} {Adjacency} {Eigenvalue} of a {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {467--493},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a7/}
}
TY  - JOUR
AU  - Cioabă, Sebastian M.
AU  - Elzinga, Randall J.
AU  - Gregory, David A.
TI  - Some Observations on the Smallest Adjacency Eigenvalue of a Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 467
EP  - 493
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a7/
LA  - en
ID  - DMGT_2020_40_2_a7
ER  - 
%0 Journal Article
%A Cioabă, Sebastian M.
%A Elzinga, Randall J.
%A Gregory, David A.
%T Some Observations on the Smallest Adjacency Eigenvalue of a Graph
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 467-493
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a7/
%G en
%F DMGT_2020_40_2_a7
Cioabă, Sebastian M.; Elzinga, Randall J.; Gregory, David A. Some Observations on the Smallest Adjacency Eigenvalue of a Graph. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 467-493. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a7/

[1] N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986) 83–96. doi:10.1007/BF02579166

[2] N. Alon, I. Benjamini, A. Lubetzky and S. Sodin, Non-backtracking random walks mix faster, Commun. Contemp. Math. 9 (2007) 585–603. doi:10.1142/S0219199707002551

[3] N. Alon and V.D. Milman, λ 1, isoperimetric inequalities for graphs and superconcentrators, J. Combin. Theory Ser. B 38 (1985) 73–88. doi:10.1016/0095-8956(85)90092-9

[4] R. Aharoni, N. Alon and E. Berger, Eigenvalues of K1,k-free graphs and the connectivity of their independence complexes, J. Graph Theory 83 (2016) 384–391. doi:10.1002/jgt.22004

[5] N. Alon and B. Sudakov, Bipartite subgraphs and the smallest eigenvalue, Combin. Probab. Comput. 9 (2000) 1–12. doi:10.1017/S0963548399004071

[6] F.K. Bell, D. Cvetković, P. Rowlinson and S.K. Simić, Graphs for which the least eigenvalue is minimal I, Linear Algebra Appl. 429 (2008) 234–241. doi:10.1016/j.laa.2008.02.032

[7] F.K. Bell, D. Cvetković, P. Rowlinson and S.K. Simić, Graphs for which the least eigenvalue is minimal II, Linear Algebra Appl. 429 (2008) 2168–2179. doi:10.1016/j.laa.2008.06.018

[8] N. Biggs, Algebraic Graph Theory, 2nd Edition (Cambridge University Press, Cambridge 1993).

[9] R.C. Bose, Strongly regular graphs, partial geometries, and partially balanced designs, Pacific J. Math. 13 (1963) 389–419. doi:10.2140/pjm.1963.13.389

[10] A.E. Brouwer, S.M. Cioabă, F. Ihringer and M. McGinnis, The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters, J. Combin. Theory Ser. B 133 (2018) 88–121. doi:10.1016/j.jctb.2018.04.005

[11] A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, New York, 2012). doi:10.1007/978-1-4614-1939-6

[12] T. Ceccherini-Silberstein, F. Scarabotti and F. Tolli, Filippo, Harmonic Analysis on Finite Groups. Representation Theory, Gelfand Pairs and Markov Chains, Cambridge Studies in Advanced Mathematics 108 (Cambridge University Press, Cambridge, 2008).

[13] M. Chudnovsky and P. Seymour, The structure of claw-free graphs, Surveys in Combinatorics, London Math. Soc. Lecture Note Ser. 327 (2005) 153–172. doi:10.1017/CBO9780511734885.008

[14] S.M. Cioabă, Eigenvalues, Expanders and Gaps between Primes, Ph.D. Thesis (Queen’s University at Kingston, Canada, 2005).

[15] S.M. Cioabă, On the extreme eigenvalues of regular graphs, J. Combin. Theory, Ser. B 96 (2006) 367–373. doi:10.1016/j.jctb.2005.09.002

[16] S.M. Cioabă, The spectral radius and maximum degree of irregular graphs, Electron. J. Combin. 14 (2007) #R38.

[17] S.M. Cioabă and P. Xu, Mixing rates of random walks with little backtracking, Contemp. Math. 655 (2015) 27–58. doi:10.1090/conm/655/13202

[18] D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, Theory and Applications (Academic Press, New York, 1980).

[19] D.M. Cvetković, M. Doob and S. Simić, Generalized line graphs, J. Graph Theory 5 (1981) 385–399. doi:10.1002/jgt.3190050408

[20] D.M. Cvetković, P. Rowlinson and S. Simić, Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue -2, London Math. Soc. Lecture Note Ser. 314 (Cambridge University Press, Cambridge, 2004).

[21] D.M. Cvetković, P. Rowlinson and S. Simić, Graphs with least eigenvalue − 2 : a new proof of the 31 forbidden subgraphs theorem, Des. Codes Cryptogr. 34 (2005) 229–240. doi:10.1007/s10623-004-4856-5

[22] C. Godsil and K. Meagher, Erdős-Ko-Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics 149 (Cambridge University Press, Cambridge, 2016). doi:10.1017/CBO9781316414958.

[23] C. Godsil and G. Royle, Algebraic Graph Theory (Springer-Verlag, New York, 2001).

[24] M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 (1995) 1115–1145. doi:10.1111/j.1553-2712.1995.tb03162.x

[25] A.J. Hoffman, On graphs whose least eigenvalues exceed −1 − \(\sqrt{2}\), Linear Algebra Appl. 16 (1977) 153–165. doi:10.1016/0024-3795(77)90027-1

[26] H. Karlo, How good is the Goemans–Williamson max cut algorithm?, SIAM J. Comput. 20 (1999) 336–350. doi:10.1137/S0097539797321481

[27] F. Knox and B. Mohar, Fractional decompositions and smallest-eigenvalue separation, Electron. J. Combin. 26 (2019) #P4.41.

[28] J. Krausz, Demonstration nouvelle d’une théorèm de Whitney sur les reseaux, Mat. Fiz. Lapok 50 (1943) 75–89.

[29] W.-C. Winnie Li, Character sums and Abelian Ramanujan graphs, J. Number Theory 41 (1992) 199–217. doi:10.1016/0022-314X(92)90120-E

[30] N. Linial, Personal communication to the 1st author, (2004).

[31] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory IT-25 (1979) 1–7. doi:10.1109/TIT.1979.1055985

[32] V. Nikiforov, The spectral radius of subgraphs of regular graphs, Electron. J. Combin. 14 (2007) #N20.

[33] N.J. Pullman, H. Shank and W.D. Wallis, Cliques coverings of graphs V : maximal cliques partitions, Bull. Aust. Math. Soc. 25 (1982) 337–356. doi:10.1017/S0004972700005414

[34] L. Trevisan, Max cut and the smallest eigenvalue, SIAM J. Comput. 41 (2012) 1769–1786. doi:10.1137/090773714

[35] J.H. van Lint and R.M. Wilson, A Course in Combinatorics, Edition 2 (Cambridge University Press, Cambridge, 2002). doi:10.1017/CBO9780511987045