谱图理论中的未解决问题

doi:10.15960/j.cnki.issn.1007-6093.2023.04.003

摘要/Abstract

摘要：

谱图理论是图论中一个迷人的领域, 其利用与图相关的矩阵的特征值和特征向量来研究图的性质.本文收集了谱图理论中的若干公开问题和猜想, 按照内容的相关性将其分为20个主题.本文主要关注图的邻接矩阵中的相关问题, 并对这些问题和猜想的研究进展做了简要的梳理.

关键词: 特征值, 谱半径, 邻接矩阵, 谱图理论

Abstract:

Spectral graph theory is a captivating area of graph theory that employs the eigenvalues and eigenvectors of matrices associated with graphs to study them. In this paper, we present a collection of 20 topics in spectral graph theory, covering a range of open problems and conjectures. Our focus is primarily on the adjacency matrix of graphs, and for each topic, we provide a brief historical overview.

Key words: eigenvalues, spectral radius, adjacency matrix, spectral graph theory

中图分类号:

O157.5

刘乐乐, 宁博. 谱图理论中的未解决问题[J]. 运筹学学报, 2023, 27(4): 33-60.

Lele LIU, Bo NING. Unsolved problems in spectral graph theory[J]. Operations Research Transactions, 2023, 27(4): 33-60.

图/表 2

参考文献 153

1	Bondy J A , Murty U . Graph Theory[M]. London: Springer-Verlag, 2008.
2	Hong Y . A bound on the spectral radius of graphs[J]. Linear Algebra and its Applications, 1988, 108, 135- 140. doi: 10.1016/0024-3795(88)90183-8
3	Hong Y . Bounds on eigenvalues of graphs[J]. Discrete Mathematics, 1993, 123, 65- 74. doi: 10.1016/0012-365X(93)90007-G
4	Elphick C , Farber M , Goldberg F , et al. Conjectured bounds for the sum of squares of positive eigenvalues of a graph[J]. Discrete Mathematics, 2016, 339 (9): 2215- 2223. doi: 10.1016/j.disc.2016.01.021
5	Guo J M , Wang C C . The estimation of the bound of the sum of squares of positive (negative) eigenvalues of a graph[J]. Advances in Mathematics (China), 2022, 51 (1): 69- 75.
6	Nikiforov V . The energy of graphs and matrices[J]. Journal of Mathematical Analysis and Applications, 2007, 326, 1472- 1475. doi: 10.1016/j.jmaa.2006.03.072
7	Abiad A , de Lima L , Desai D N , et al. Positive and negative square energies of graphs[J]. Electronic Journal of Linear Algebra, 2023, 39, 307- 326. doi: 10.13001/ela.2023.7827
8	Wilf H . Spectral bounds for the clique and independence numbers of graphs[J]. Journal of Combinatorial Theory, Series B, 1986, 40, 113- 117. doi: 10.1016/0095-8956(86)90069-9
9	Elphick C, Wocjan P. Conjectured lower bound for the clique number of a graph [J]. 2018, arXiv: 1804.03752.
10	Bollobás B , Nikiforov V . Cliques and the spectral radius[J]. Journal of Combinatorial Theory, Series B, 2007, 97, 859- 865. doi: 10.1016/j.jctb.2006.12.002
11	Nosal E. Eigenvalues of Graphs [D]. Alberta: University of Calgary, 1970.
12	Nikiforov V . Some inequalities for the largest eigenvalue of a graph[J]. Combinatorics, Probability and Computing, 2002, 11, 179- 189. doi: 10.1017/S0963548301004928
13	Edwards C , Elphick C . Lower bounds for the clique and the chromatic number of a graph[J]. Discrete Applied Mathematics, 1983, 5, 51- 64. doi: 10.1016/0166-218X(83)90015-X
14	Lin H Q , Ning B , Wu B . Eigenvalues and triangles in graphs[J]. Combinatorics, Probability and Computing, 2021, 30 (2): 258- 270. doi: 10.1017/S0963548320000462
15	Li S C , Sun W T , Yu Y T . Adjacency eigenvalues of graphs without short odd cycles[J]. Discrete Mathematics, 2022, 345, Paper No. 112633. doi: 10.1016/j.disc.2021.112633
16	Ando T , Lin M H . Proof of a conjectured lower bound on the chromatic number of a graph[J]. Linear Algebra and its Applications, 2015, 485, 480- 484. doi: 10.1016/j.laa.2015.08.007
17	Elphick C, Linz W, Wocjan P. Generalising a conjecture due to Bollobás and Nikiforov [J]. 2021, arXiv: 2101.05229.
18	Schwenk A J , Wilson R J . On the eigenvalues of a graph[M]. London: Academic Press, 1978: 307- 336.
19	Cao D , Vince A . The spectral radius of a planar graph[J]. Linear Algebra and its Applications, 1993, 187, 251- 257. doi: 10.1016/0024-3795(93)90139-F
20	Hong Y . On the spectral radius and the genus of graphs[J]. Journal of Combinatorial Theory, Series B, 1995, 65 (2): 262- 268. doi: 10.1006/jctb.1995.1053
21	Ellingham M N , Zha X . The spectral radius of graphs on surfaces[J]. Journal of Combinatorial Theory, Series B, 2000, 78 (1): 45- 56. doi: 10.1006/jctb.1999.1926
22	Boots B N , Royle G F . A conjecture on the maximum value of the principal eigenvalue of a planar graph[J]. Geographical Analysis, 1991, 23 (3): 276- 282. doi: 10.1111/j.1538-4632.1991.tb00239.x
23	Tait M , Tobin J . Three conjectures in extremal spectral graph theory[J]. Journal of Combinatorial Theory, Series B, 2017, 126, 137- 161. doi: 10.1016/j.jctb.2017.04.006
24	Guiduli B. Spectral extrema for graphs [D]. Chicago: University of Chicago, 1996.
25	Ellingham M N , Lu L Y , Wang Z Y . Maximum spectral radius of outerplanar 3-uniform hypergraphs[J]. Journal of Graph Theory, 2022, 100 (4): 671- 685. doi: 10.1002/jgt.22801
26	Nikiforov V . A spectral Erdős-Stone-Bollobás theorem[J]. Combinatorics, Probability and Computing, 2009, 18 (3): 455- 458. doi: 10.1017/S0963548309009687
27	Erdős P , Stone A H . On the structure of linear graphs[J]. Bulletin of the American Mathematical Society, 1946, 52, 1087- 1091. doi: 10.1090/S0002-9904-1946-08715-7
28	Erdős P , Simonovits M . A limit theorem in graph theory[J]. Studia Scientiarum Mathematicarum Hungarica, 1966, 1, 51- 57.
29	Turán P . Research problems[J]. A Magyar Tudományos Akadémia. Matematikai Kutató Intézetének Közleményei, 1961, 6, 417- 423.
30	Nikiforov V . Bounds on graph eigenvalues Ⅱ[J]. Linear Algebra and its Applications, 2007, 427, 183- 189. doi: 10.1016/j.laa.2007.07.010
31	Nikiforov V . The maximum spectral radius of C₄-free graphs of given order and size[J]. Linear Algebra and its Applications, 2009, 430, 2898- 2905. doi: 10.1016/j.laa.2009.01.002
32	Zhai M Q , Wang B . Proof of a conjecture on the spectral radius of C₄-free graphs[J]. Linear Algebra and its Applications, 2012, 437, 1641- 1647. doi: 10.1016/j.laa.2012.05.006
33	Nikiforov V . The spectral radius of graphs without paths and cycles of specified length[J]. Linear Algebra and its Applications, 2010, 432, 2243- 2256. doi: 10.1016/j.laa.2009.05.023
34	Zhai M Q , Lin H Q . Spectral extrema of graphs: forbidden hexagon[J]. Discrete Mathematics, 2020, 343, Paper No. 112028. doi: 10.1016/j.disc.2020.112028
35	Cioabă S M, Desai D N, Tait M. The spectral even cycle problem [J]. 2022, arXiv: 2205.00990.
36	Li B L , Ning B . Stability of Woodall's theorem and spectral conditions for large cycles[J]. Electronic Journal of Combinatorics, 2023, 30 (1): P1.39. doi: 10.37236/11641
37	Zhai M Q , Lin H Q , Shu J L . Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs[J]. European Journal of Combinatorics, 2021, 95, Paper No. 103322. doi: 10.1016/j.ejc.2021.103322
38	Min G , Lou Z Z , Huang Q X . A sharp upper bound on the spectral radius of C₅-free/C₆-free graphs with given size[J]. Linear Algebra and its Applications, 2022, 640, 162- 178. doi: 10.1016/j.laa.2022.01.016
39	Sun W T , Li S C , Wei W . Extensions on spectral extrema of C₅/C₆-free graphs with given size[J]. Discrete Mathematics, 2023, 346 (12): Paper No. 113591. doi: 10.1016/j.disc.2023.113591
40	Dirac A G . Some theorems on abstract graphs[J]. Proceedings of the London Mathematical Society, 1952, 2, 69- 81.
41	Bondy J A . Pancyclic graphs Ⅰ[J]. Journal of Combinatorial Theory, Series B, 1971, 11, 80- 84. doi: 10.1016/0095-8956(71)90016-5
42	Ore O . Note on Hamilton circuits[J]. American Mathematical Monthly, 1960, 67, Paper No. 55. doi: 10.2307/2308928
43	Bollobás B. Extremal graph theory [M]// London Mathematical Society Monographs, New York: Academic Press Inc., 1978.
44	Nikiforov V . A spectral condition for odd cycles in graphs[J]. Linear Algebra and its Applications, 2008, 428 (7): 1492- 1498. doi: 10.1016/j.laa.2007.09.029
45	Ning B , Peng X . Extensions of the Erdős-Gallai theorem and Luo's theorem[J]. Combinatorics, Probability and Computing, 2020, 29 (1): 128- 136. doi: 10.1017/S0963548319000269
46	Zhai M Q , Lin H Q . A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs[J]. Journal of Graph Theory, 2023, 102 (3): 502- 520. doi: 10.1002/jgt.22883
47	Li B L , Ning B . Eigenvalues and cycles of consecutive lengths[J]. Journal of Graph Theory, 2023, 103, 486- 492. doi: 10.1002/jgt.22930
48	Allen P , łuczak T , Polcyn J , et al. The Ramsey number of a long even cycle versus a star[J]. Journal of Combinatorial Theory, Series B, 2023, 162, 144- 153. doi: 10.1016/j.jctb.2023.05.001
49	Voss H , Zuluaga C . Maximale gerade und ungerade kreise in graphen Ⅰ (German)[J]. Wissenschaftliche Zeitschrift Technische Hochschule Ilmenau, 1977, 23, 57- 70.
50	Zhang Z , Zhao Y . A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs[J]. Discrete Mathematics, 2023, 346 (6): Paper No. 113365. doi: 10.1016/j.disc.2023.113365
51	Chvátal V . Tough graphs and Hamiltonian circuits[J]. Discrete Mathematics, 1973, 5, 215- 228. doi: 10.1016/0012-365X(73)90138-6
52	Bauer D , Broersma H , Schmeichel E . Toughness in graphs——a survey[J]. Graphs and Combinatorics, 2006, 22 (1): 1- 35. doi: 10.1007/s00373-006-0649-0
53	Alon N . Tough Ramsey graphs without short cycles[J]. Journal of Algebraic Combinatorics, 1995, 4, 189- 195. doi: 10.1023/A:1022453926717
54	Brouwer A E . Toughness and spectrum of a graph[J]. Linear Algebra and its Applications, 1995, 226-228, 267- 271. doi: 10.1016/0024-3795(95)00154-J
55	Brouwer A E . Spectrum and connectivity of graphs[J]. Centrum voor Wiskunde en Informatica. Centre for Mathematics and Computer Science. CWI Quarterly, 1996, 9, 37- 40.
56	Gu X F . A proof of Brouwer's toughness conjecture[J]. SIAM Journal on Discrete Mathematics, 2021, 35 (2): 948- 952. doi: 10.1137/20M1372652
57	Haemers W H. Toughness conjecture [EB/OL]. (2021-01-01)[2023-05-02]. https://www.researchgate.net/publication/348437253_Toughness_conjecture
58	Gu X F , Haemers W H . Graph toughness from Laplacian eigenvalues[J]. Algebraic Combinatorics, 2022, 5 (1): 53- 61. doi: 10.5802/alco.197
59	Krivelevich M, Sudakov B. Pseudo-random graphs [M]// Graphs and Numbers, Berlin: Springer, 2006: 199-262.
60	Krivelevich M , Sudakov B . Sparse pseudo-random graphs are Hamiltonian[J]. Journal of Graph Theory, 2003, 42 (1): 17- 33. doi: 10.1002/jgt.10065
61	Glock S, Correia D M, Sudakov B. Hamilton cycles in pseudorandom graphs [J]. 2023, arXiv: 2303.05356.
62	Brandt S , Broersma H , Diestel R , et al. Global connectivity and expansion: Long cycles and factors in f-connected graphs[J]. Combinatorica, 2006, 26, 17- 36. doi: 10.1007/s00493-006-0002-5
63	Erdős P . Some theorems on graphs[J]. Riveon Lematematika, 1955, 9, 13- 17.
64	Erdős P . On a theorem of Rademacher-Turán[J]. Illinois Journal of Mathematics, 1962, 6, 122- 127.
65	Erdős P . On the number of complete subgraphs contained in certain graphs[J]. A Magyar Tudományos Akadémia. Matematikai Kutató Intézetének Közleményei, 1962, 7, 459- 464.
66	Lovász L, Simonovits M. On the number of complete subgraphs of a graph Ⅱ [M]// Studies in Pure Math, Boston: Birkhäuser, 1983: 459-495.
67	Mubayi D . Counting substructures Ⅰ: Color critical graphs[J]. Advances in Mathematics, 2010, 225 (5): 2731- 2740. doi: 10.1016/j.aim.2010.05.013
68	Ning B , Zhai M Q . Counting substructures and eigenvalues Ⅰ: Triangles[J]. European Journal of Combinatorics, 2023, 110, Paper No. 103685. doi: 10.1016/j.ejc.2023.103685
69	Ning B, Zhai M Q. Counting substructures and eigenvalues Ⅱ: Quadrilaterals [J]. 2022, arXiv: 2112.15279.
70	Cioabă S M . The spectral radius and the maximum degree of irregular graphs[J]. Electronic Journal of Combinatorics, 2007, 14, R38. doi: 10.37236/956
71	Cioabă S M , Gregory D A , Nikiforov V . Extreme eigenvalues of nonregular graphs[J]. Journal of Combinatorial Theory. Series B, 2007, 97, 483- 486. doi: 10.1016/j.jctb.2006.07.006
72	Nikiforov V. Spectral radius and maximum degree of connected graphs [J]. 2018, arXiv: 0602028.
73	Shi L S . Bounds on the (Laplacian) spectral radius of graphs[J]. Linear Algebra and its Applications, 2007, 422, 755- 770.
74	Shi L S . The spectral radius of irregular graphs[J]. Linear Algebra and its Applications, 2009, 431, 189- 196.
75	Stevanović D . The largest eigenvalue of nonregular graphs[J]. Journal of Combinatorial Theory, Series B, 2004, 91, 143- 146.
76	Zhang X D . Eigenvectors and eigenvalues of nonregular graphs[J]. Linear Algebra and its Applications, 2005, 409, 79- 86.
77	Zhang W Q . A new result on spectral radius and maximum degree of irregular graphs[J]. Graphs and Combinatorics, 2021, 37, 1103- 1119.
78	Liu B L , Shen J , Wang X M . On the largest eigenvalue of non-regular graphs[J]. Journal of Combinatorial Theory, Series B, 2007, 97, 1010- 1018.
79	Liu L L. Extremal spectral radius of nonregular graphs with prescribed maximum degree [J]. 2022, arXiv: 2203.10245.
80	Liu B L , Li G . A note on the largest eigenvalue of non-regular graphs[J]. Electronic Journal of Linear Algebra, 2008, 17, 54- 61.
81	Collatz L , Sinogowitz U . Spektren endlicher grafen[J]. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 1957, 21, 63- 77.
82	Lovász L , Pelikán J . On the eigenvalues of trees[J]. Periodica Mathematica Hungarica, 1973, 3, 175- 182.
83	Simić S K . On the largest eigenvalue of bicyclic graphs[J]. Publications de l'Institut Mathématique, 1989, 46 (60): 101- 106.
84	Cioabă S M. The principal eigenvector of a connected graph, in: Spectral Graph Theory Online Conference [EB/OL]. (2021-04-28)[2023-05-02]. http://spectralgraphtheory.org/sgt-online-program/.
85	Belardo F , Cioabă S M , Koolen J , et al. Open problems in the spectral theory of signed graphs[J]. The Art of Discrete and Applied Mathematics, 2018, 1, P2.10.
86	Bilu Y , Linial N . Lifts, discrepancy and nearly optimal spectral gap[J]. Combinatorica, 2006, 26, 495- 519.
87	Marcus A W , Spielman D A , Srivastava N . Interlacing families Ⅰ: Bipartite Ramanujan graphs of all degrees[J]. Annals of Mathematics, 2015, 182, 307- 325.
88	Bollobás B , Lee J , Letzter S . Eigenvalues of subgraphs of the cube[J]. European Journal of Combinatorics, 2018, 70, 125- 148.
89	Friedman J , Tillich J P . Generalized Alon-Boppana theorems and error-correcting codes[J]. SIAM Journal on Discrete Mathematics, 2005, 19 (3): 700- 718.
90	Erdős P , Hajnal A , Moon J . A problem in graph theory[J]. American Mathematical Monthly, 1964, 71, 1107- 1110.
91	Currie B L , Faudree J R , Faudree R J , et al. A survey of minimum saturated graphs[J]. Electronic Journal of Combinatorics, 2021, DS19.
92	Kim J , Kim S , Kostochka A V , et al. The minimum spectral radius of K_r+1-saturated graphs[J]. Discrete Mathematics, 2020, 343, Paper No. 112068.
93	Kim J , Kostochka A V , O S , et al. A sharp lower bound for the spectral radius in K₄-saturated graphs[J]. Discrete Mathematics, 2023, 346, Paper No. 113231.
94	Bai H . The Grone-Merris conjecture[J]. Transactions of the American Mathematical Society, 2011, 363, 4463- 4474.
95	Brouwer A E , Haemers W H . Spectra of Graphs[M]. New York: Springer-Verlag, 2012.
96	Haemers W H , Mohammadian A , Tayfeh-Rezaie B . On the sum of Laplacian eigenvalues of graphs[J]. Linear Algebra and its Applications, 2010, 432, 2214- 2221.
97	Li W J , Guo J M . On the full Brouwer's Laplacian spectrum conjecture[J]. Discrete Mathematics, 2022, 345, Paper No. 113078.
98	Chen X D . On Brouwer's conjecture for the sum of k largest Laplacian eigenvalues of graphs[J]. Linear Algebra and its Applications, 2019, 578, 402- 410.
99	Rocha I , Trevisan V . Bounding the sum of the largest Laplacian eigenvalues of graphs[J]. Discrete Applied Mathematics, 2014, 170, 95- 103.
100	Du Z B , Zhou B . Upper bounds for the sum of Laplacian eigenvalues of graphs[J]. Linear Algebra and its Applications, 2012, 436, 3672- 3683.
101	Wang S Z , Huang Y F , Liu B L . On a conjecture for the sum of Laplacian eigenvalues[J]. Mathematical and Computer Modelling, 2012, 56, 60- 68.
102	Mayank. On variants of the Grone-Merris conjecture [D]. Eindhoven, Eindhoven University of Technology, 2010.
103	Blinovsky V, Speranca L D. Proof of Brouwer's conjecture [J]. 2022, arXiv: 1908.08534v4.
104	Chen X D . Improved results on Brouwer's conjecture for sum of the Laplacian eigenvalues of a graph[J]. Linear Algebra and its Applications, 2018, 557, 327- 338.
105	Cooper J N . Constraints on Brouwer's Laplacian spectrum conjecture[J]. Linear Algebra and its Applications, 2021, 615, 11- 27.
106	Ganie H A , Pirzada S . Corrigendum to "on the sum of the laplacian eigenvalues of a graph and Brouwer's conjecture"[J]. Linear Algebra and its Applications, 2018, 538, 228- 230.
107	Ganie H A , Alghamdi A M , Pirzada S . On the sum of the Laplacian eigenvalues of a graph and Brouwer's conjecture[J]. Linear Algebra and its Applications, 2016, 501, 376- 389.
108	Ganie H A , Pirzada S , Rather B A , et al. Further developments on Brouwer's conjecture for the sum of Laplacian eigenvalues of graphs[J]. Linear Algebra and its Applications, 2020, 588, 1- 18.
109	Rocha I . Brouwer's conjecture holds asymptotically almost surely[J]. Linear Algebra and its Applications, 2020, 597, 198- 205.
110	Cvetković D , Doob M , Sachs H . Spectra of Graphs: Theory and Application[M]. Heidelberg-Leipzig: Johann Ambrosius Barth Verlag, 1995.
111	Stanić Z . Graphs with small spectral gap[J]. Electronic Journal of Linear Algebra, 2013, 26, 417- 432.
112	Aksoy S G , Chung F , Tait M , et al. The maximum relaxation time of a random walk[J]. Advances in Applied Mathematics, 2018, 101, 1- 14.
113	Aldous D, Fill J. Reversible Markov Chains and Random Walks on Graphs [EB/OL]. (2002-12-01)[2023-05-02]. https://mathematicaster.org/teaching/lcs22/aldous_markov.pdf.
114	Brand C , Guiduli B , Imrich W . Characterization of trivalent graphs with minimal eigenvalue gap[J]. Croatica Chemica Acta, 2007, 80, 193- 201.
115	Abdi M , Ghorbani E . Quartic graphs with minimum spectral gap[J]. Journal of Graph Theory, 2023, 102, 205- 233.
116	Jovović I , Koledin T , Stanić Z . Trees with small spectral gap[J]. Ars Mathematica Contemporanea, 2018, 14, 197- 207.
117	Li X L , Shi Y T , Gutman I . Graph Energy[M]. New York: Springer, 2012.
118	Aouchiche M , Hansen P . A survey of automated conjectures in spectral graph theory[J]. Linear Algebra and its Applications, 2010, 432, 2293- 2322.
119	Godsil C , Royle G . Graduate Texts in Mathematics 207: Algebraic Graph Theory[M]. New York: Springer-Verlag, 2001.
120	Akbari S , Hosseinzadeh M A . A short proof for graph energy is at least twice of minimum degree[J]. MATCH. Communications in Mathematical and in Computer Chemistry, 2020, 83, 631- 633.
121	Al-Yakoob S , Filipovski S , Stevanović D . Proofs of a few special cases of a conjecture on energy of non-singular graphs,[J]. MATCH. Communications in Mathematical and in Computer Chemistry, 2021, 86, 577- 586.
122	Erdős P. Problems and results in graph theory and combinatorial analysis [C]// Proceedings of the fifth british combinatorial conference, Congressus numerantium, 1976, 15: 169-192.
123	Erdős P . Some old and new problems in various branches of combinatorics[J]. Discrete Mathematics, 1997, 165-166, 227- 231.
124	Bedenknecht W , Mota G O , Reiher C , et al. On the local density problem for graphs of given odd-girth[J]. Journal of Graph Theory, 2019, 90 (2): 137- 149.
125	Erdős P , Faudree R J , Rousseau C C , et al. A local density condition for triangles[J]. Discrete Mathematics, 1994, 127, 153- 161.
126	Keevash P , Sudakov B . Sparse halves in triangle-free graphs[J]. Journal of Combinatorial Theory, Series B, 2006, 96 (4): 614- 620.
127	Norin S , Yepremyan L . Sparse halves in dense triangle-free graphs[J]. Journal of Combinatorial Theory, Series B, 2015, 115, 1- 25.
128	Razborov A A . More about sparse halves in triangle-free graphs[J]. Sbornik Mathematics, 2022, 213 (1): 109- 128.
129	Alon N . Bipartite subgraphs[J]. Combinatorica, 1996, 16 (3): 301- 311.
130	Erdős P , Faudree R , Pach J , et al. How to make a graph bipartite[J]. Journal of Combinatorial Theory, Series B, 1988, 45 (1): 86- 98.
131	Erdős P, Győri E, Simonovits M. How many edges should be deleted to make a triangle-free graph bipartite? [M]// Sets, Graphs and Numbers 60. Budapest: Colloq. Math. Soc. János Bolyai, 1991.
132	Shearer J B . A note on bipartite subgraphs of triangle-free graphs[J]. Random Structures & Algorithms, 1992, 3 (2): 223- 226.
133	Balogh J, Clemen F C, Lidický B. Max cuts in triangle-free graphs [J]. 2021, arXiv: 2103.14179.
134	Brandt S . The local density of triangle-free graphs[J]. Discrete Mathematics, 1998, 183 (1-3): 17- 25.
135	Balogh J , Clemen F C , Lidický B , et al. The spectrum of triangle-free graphs[J]. SIAM Journal on Discrete Mathematics, 2023, 37 (2): 1173- 1179.
136	Csikvári P . Note on the sum of the smallest and largest eigenvalues of a triangle-free graph[J]. Linear Algebra and its Applications, 2022, 650, 92- 97.
137	de Lima L , Nikiforov V , Oliveira C . The clique number and the smallest Q-eigenvalue of graphs[J]. Discrete Mathematics, 2016, 339, 1744- 1752.
138	Oboudi M R . On a conjecture related to the smallest signless Laplacian eigenvalue of graphs[J]. Linear and Multilinear Algebra, 2022, 70 (19): 4425- 4431.
139	Powers D L . Bounds on graph eigenvalues[J]. Linear Algebra and its Applications, 1989, 117, 1- 6.
140	Hong Y . Bound of eigenvalues of a graph[J]. Acta Mathematicae Applicatae Sinica, 1988, 432 (4): 165- 168.
141	Nikiforov V . Extrema of graph eigenvalues[J]. Linear Algebra and its Applications, 2015, 482, 158- 190.
142	Linz W . Improved lower bounds on the extrema of eigenvalues of graphs[J]. Graphs and Combinatorics, 2023, 39, Paper No. 82.
143	Fowler P W , Pisanski T . HOMO—LUMO maps for fullerenes[J]. Acta Chimica Slovenica, 2010, 57, 513- 517.
144	Fowler P W , Pisanski T . HOMO—LUMO maps for chemical graphs[J]. Match Communications in Mathematical and in Computer Chemistry, 2010, 64, 373- 390.
145	Clemente G P , Cornaro A . Bounding the HL-index of a graph: A majorization approach[J]. Journal of Inequalities and Applications, 2016, 285.
146	Jaklič G , Fowler P W , Pisanski T . HL-index of a graph[J]. Ars Mathematica Contemporanea, 2012, 5, 99- 115.
147	Li X L , Li Y , Shi Y T , et al. Note on the HOMO—LUMO index of graphs[J]. Match Communications in Mathematical and in Computer Chemistry, 2013, 70, 85- 96.
148	Mohar B . Median eigenvalues and the HOMO—LUMO index of graphs[J]. Journal of Combinatorial Theory, Series B, 2015, 112, 78- 92.
149	Mohar B . Median eigenvalues of bipartite planar graphs[J]. Match Communications in Mathematical and in Computer Chemistry, 2013, 70, 79- 84.
150	Mohar B . Median eigenvalues of bipartite subcubic graphs[J]. Combinatorics, Probability and Computing, 2016, 25, 768- 790.
151	Cioabă S M . A necessary and sufficient eigenvector condition for a connected graph to be bipartite[J]. Electronic Journal of Linear Algebra, 2010, 20, 351- 353.
152	Clark G J. Comparing eigenvector and degree dispersion with theprincipal ratio of a graph [J/OL]. (2022-12-20)[2023-05-02]. Linear and Multilinear Algebra, 2022. DOI: 10.1080/03081087.2022.2158171.
153	Rücker G , Rücker C , Gutman I . On kites, comets, and stars. sums of eigenvector coefficientsin (molecular) graphs[J]. Zeitschrift für Naturforschung A, 2002, 57 (3-4): 143- 153.

$ n $	$ n {\leqslant} 8 $	$ 9 {\leqslant} n {\leqslant} 11 $	$ 12 {\leqslant} n {\leqslant} 15 $	$ 16 {\leqslant} n {\leqslant} 20 $
The unique tree	$ C(1, n-2) (\cong P_n) $	$ C(2, n-4) $	$ C(3, n-6) $	$ C(4, n-8) $

[1]	贾会才, 宋宏业. 基于Wiener指数和Harary指数的泛圈图的充分条件[J]. 运筹学学报, 2023, 27(3): 169-177.
[2]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[3]	余桂东, 孙威, 芦兴庭. 补图具有悬挂点且连通的图的最小特征值[J]. 运筹学学报, 2019, 23(1): 90-96.
[4]	张涛, 白延琴. 基于拉普拉斯谱确定的两类树[J]. 运筹学学报, 2017, 21(1): 103-110.
[5]	余桂东, 周甫, 刘琦. 可迹图的谱充分条件[J]. 运筹学学报, 2017, 21(1): 118-124.
[6]	徐凤, 凌晨. 高阶张量Pareto-特征值的若干性质[J]. 运筹学学报, 2015, 19(3): 34-41.
[7]	陈琳, 黄琼湘. 恰有两个Q-主特征值的三圈图[J]. 运筹学学报, 2014, 18(3): 13-32.
[8]	徐薇薇, 王文环. 双圈图的最大Estrada指数[J]. 运筹学学报, 2014, 18(2): 111-118.
[9]	李浙宁，凌晨，王宜举，杨庆之. 张量分析和多项式优化的若干进展[J]. 运筹学学报, 2014, 18(1): 134-148.
[10]	余桂东，范益政. 补图为2-点或2-边连通的图的最小特征值[J]. 运筹学学报, 2013, 17(2): 81-88.
[11]	王力工, 陈彦青. Q整图新类[J]. 运筹学学报, 2012, 16(2): 23-31.
[12]	陈艳, 袁西英, 韩苗苗. 关于三圈图的拉普拉斯谱半径的一些结果[J]. 运筹学学报, 2011, 15(4): 1-8.
[13]	陈琳, 黄琼湘. 给定顶点数和边数的连通图的Q-谱半径[J]. 运筹学学报, 2011, (3): 19-28.
[14]	陈琳黄琼湘. 给定顶点数和边数的连通图的Q-谱半径的界[J]. 运筹学学报, 2011, 15(3): 19-28.
[15]	吴廷增, 扈生彪. m重似星树的谱半径[J]. 运筹学学报, 2011, 15(3): 45-50.