Some new aspects of main eigenvalues of graphs
Tóm tắt
An eigenvalue of the adjacency matrix of a graph is said to be main if the all-1 vector is non-orthogonal to the associated eigenspace. This paper explores some new aspects of the study of main eigenvalues of graphs, investigating specifically cones over strongly regular graphs and graphs for which the least eigenvalue is non-main. In this case, we characterize paths and trees with diameter-3 satisfying the property. We may note that the importance of least eigenvalues of graphs for the equilibria of social and economic networks was recently uncovered in literature.
Tài liệu tham khảo
Allouch N (2017) The cost of segregation in (social) networks. Games Econ Behav 106:329–342
Bramoullé Y, Kranton R, D’Amours M (2014) Strategic interaction and networks. Am Econ Rev 104(3):898–930
Bridges WG, Mena RA (1979) Multiplicative designs II. Uniform normal and related structures. J Combin Theory A 27:269–281
Brouwer AE, Haemers WH (2012) Spectra of graphs. Springer, New York
Cardoso DM, Pinheiro SJ (2009) Spectral upper bounds on the size of \(k\)-regular induced subgraphs. Electron Notes Discrete Math 32:3–10
Cardoso DM, Rowlinson P (2010) Spectral upper bounds for the order of a \(k\)-regular induced subgraph. Linear Algebra Appl 433(5):1031–1037
Cardoso DM, Sciriha I, Zerafa C (2010) Main eigenvalues and \((k,\tau )-\)regular sets. Linear Algebra Appl 432:2399–2408
Cheng XM, Gavrilyuk A, Greaves G, Koolen J (2016) Biregular graphs with three eigenvalues. Eur J Comb 56:57–80
Cheng XM, Greaves G, Koolen J (2018) Graphs with three eigenvalues and second largest eigenvalue at most 1. J Combin Theory B 129:55–78
Chung H, Omidi GR (2009) Graphs with three distinct eigenvalues and largest eigenvalues less than 8. Linear Algebra Appl 430:2053–2062
Cvetković D (1970) The generating function for variations with restrictions and paths of the graph and self-complementary graphs. Univ Beograd Publ Elektrotehn Fak Ser Mat Fiz 320–328:27–34
Cvetković DM (1971) Graphs and their spectra. Univ Beograd Publ Elektrotehn Fak 354–356:1–50
Cvetković D (1978) The main part of the spectrum, divisors and switching of graphs. Publ Inst Math (Beograd) 23:31–38
Cvetković DM (1978) The main part of the spectrum, divisors and switching of graphs. Publications de L’Institut Mathématique 23(37):31–38
Cvetković D, Petrić M (1984) A table of connected graphs on six vertices. Discrete Math 50:37–49
Cvetković D, Doob M, Sachs H (1979) Spectra of graphs: theory and application. Academic Press, New York
Cvetković D, Rowlinson P, Simić S (1997) Eigenspaces of graphs, Encyclopedia of mathematics and its applications, vol 66. Cambridge University Press, Cambridge
Cvetković D, Rowlinson P, Simić S (2010) An introduction to the theory of graph spectra. Cambridge University Press, Cambridge
Del-Vecchio RR, Gutman I, Trevisan V, Vinagre CTM (2009) On the spectra and energies of double-broom-like trees. Kragujevac J Sci 31:45–58
Dress A, Gutman I (2003) On the number of walks in a graph. Appl Math Lett 16:797–801
Grünewald S (2002) Harmonic trees. Appl Math Lett 15(8):1001–1004
Hagos EM (2002) Some results on graph spectra. Linear Algebra Appl 356:103–111
Hayat S, Koolen JH, Liu F, Qiaod Z (2016) A note on graphs with exactly two main eigenvalues. Linear Algebra Appl 511:318–327
Hayat S, Javaid M, Koolen JH (2017) Graphs with two main and two plain eigenvalues. Appl Anal Discrete Math 11:244–257
Hofmeister M (1983) Spectral radius and degree sequence. Math Nachr 139:211–222
Hou Y, Tian F (2006) Unicyclic graphs with exactly two main eigenvalues. Appl Math Lett 19:1143–1147
Hou Y, Zhou H (2005) Trees with exactly two main eigenvalues. Acta Hum Normal Univ 2(28):1–3 (in Chinese)
Huang X, Huang Q, Lu L (2015) Construction of graphs with exactly \(k\) main eigenvalues. Linear Algebra Appl 486:204–218
Hu Z, Li S, Zhu C (2009) Bicyclic graphs with exactly two main eigenvalues. Ph.D. thesis
Lee S, Yeh Y (1993) On eigenvalue and eigenvectors of graphs. JMC 12:121–135
Lepović M (2001) Some results on graphs with exactly two main eigenvalues. Ph.D. thesis
Mena RA, Bridges WG (1981) Multiplicative cones: a family of three eigenvalue graphs. Aequationes Mathematicae 22:208–214
Muzychuk M, Klin M (1998) On graphs with three eigenvalues. Discrete Math. 189:191–207
Nikiforov V (2006) Walks and the spectral radius of graphs. Linear Algebra Appl 418:257–268
Powers DL, Sulaiman MM (1982) The walk partition and colorations of a graph. Linear Algebra Appl 48:145–159
Rowlinson P (2007) The main eigenvalues of a graph: a survey. Appl Anal Discrete Math 1:455–471
Rowlinson P (2016) On graphs with just three distinct eigenvalues. Linear Algebra Appl 507:462–473
Rowlinson P (2017) More on graphs with just three distinct eigenvalues. Appl Anal Discrete Math 11:74–80
Shi L (2009) On graphs with given main eigenvalues. Appl Math Lett 22:1870–1874
Teranishi Y (2002) Main eigenvalues of a graph. Linear Multilinear Algebra 49:289–303
van Dam E (1998) Nonregular graphs with three eigenvalues. J Combin Theory B 73:101–118