×

zbMATH — the first resource for mathematics

Three conjectures in extremal spectral graph theory. (English) Zbl 1368.05098
Summary: We prove three conjectures regarding the maximization of spectral invariants over certain families of graphs. Our most difficult result is that the join of \(P_2\) and \(P_{n - 2}\) is the unique graph of maximum spectral radius over all planar graphs. This was conjectured by B. N. Boots and G. F. Royle [“A conjecture on the maximum value of the principal eigenvalue of a planar graph”, Geogr. Anal. 23, No. 3, 276–282 (1991; doi:10.1111/j.1538-4632.1991.tb00239.x)], and independently by D. Cao and A. Vince [Linear Algebra Appl. 187, 251–257 (1993; Zbl 0786.05056)]. Similarly, we prove a conjecture of D. Cvetković and P. Rowlinson [Linear Multilinear Algebra 28, No. 1–2, 3–33 (1990; Zbl 0744.05031)] stating that the unique outerplanar graph of maximum spectral radius is the join of a vertex and \(P_{n - 1}\). Finally, we prove a conjecture of M. Aouchiche et al. [Eur. J. Oper. Res. 191, No. 3, 661–676 (2008; Zbl 1160.90494)] stating that a pineapple graph is the unique connected graph maximizing the spectral radius minus the average degree. To prove our theorems, we use the leading eigenvector of a purported extremal graph to deduce structural properties about that graph.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Albertson, Michael O., The irregularity of a graph, Ars Combin., 46, 219-225, (1997) · Zbl 0933.05073
[2] Alon, Noga, Bipartite subgraphs, Combinatorica, 16, 3, 301-311, (1996) · Zbl 0860.05043
[3] Aouchiche, Mustapha; Bell, Francis K.; Cvetković, Dragiša; Hansen, Pierre; Rowlinson, Peter; Simić, Slobodan K.; Stevanović, Dragan, Variable neighborhood search for extremal graphs. 16. some conjectures related to the largest eigenvalue of a graph, European J. Oper. Res., 191, 3, 661-676, (2008) · Zbl 1160.90494
[4] Babai, László; Guiduli, Barry, Spectral extrema for graphs: the zarankiewicz problem, Electron. J. Combin., 16, 1, (2009) · Zbl 1186.05079
[5] Bell, Francis K., A note on the irregularity of graphs, Linear Algebra Appl., 161, 45-54, (1992) · Zbl 0776.05069
[6] Bollobás, Béla; Lee, Jonathan; Letzter, Shoham, Eigenvalues of subgraphs of the cube, (2016), preprint · Zbl 1384.05106
[7] Bollobás, Béla; Scott, Alex D., Better bounds for MAX cut, Contemporary combinatorics, 10, 185-246, (2002) · Zbl 1014.90082
[8] Boots, Barry N.; Royle, Gordon F., A conjecture on the maximum value of the principal eigenvalue of a planar graph, Geogr. Anal., 23, 3, 276-282, (1991)
[9] Brightwell, Graham; Winkler, Peter, Maximum hitting time for random walks on graphs, Random Structures Algorithms, 1, 3, 263-276, (1990) · Zbl 0744.05044
[10] Cao, Dasong; Vince, Andrew, The spectral radius of a planar graph, Linear Algebra Appl., 187, 251-257, (1993) · Zbl 0786.05056
[11] Chung, Fan RK, Spectral graph theory, vol. 92, (1997), American Mathematical Society
[12] Cioaba, Sebastian M.; Gregory, David A., Principal eigenvectors of irregular graphs, Electron. J. Linear Algebra, 16, 366-379, (2007) · Zbl 1142.05337
[13] Cvetković, Dragiša; Rowlinson, Peter, The largest eigenvalue of a graph: a survey, Linear Multilinear Algebra, 28, 1-2, 3-33, (1990) · Zbl 0744.05031
[14] Dvořák, Zdeněk; Mohar, Bojan, Spectral radius of finite and infinite planar graphs and of graphs of bounded genus, J. Combin. Theory Ser. B, 100, 6, 729-739, (2010) · Zbl 1208.05017
[15] Ellingham, Mark N.; Zha, Xiaoya, The spectral radius of graphs on surfaces, J. Combin. Theory Ser. B, 78, 1, 45-56, (2000) · Zbl 1028.05065
[16] Erdős, Paul, On sets of distances of n points, Amer. Math. Monthly, 53, 5, 248-250, (1946) · Zbl 0060.34805
[17] Favaron, Odile; Mahéo, Maryvonne; Saclé, J-F., Some eigenvalue properties in graphs (conjectures of graffiti II), Discrete Math., 111, 1, 197-220, (1993) · Zbl 0785.05065
[18] Goemans, Michel X.; Williamson, David P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 6, 1115-1145, (1995) · Zbl 0885.68088
[19] Guiduli, Barry D., Spectral extrema for graphs, (1996), University of Chicago, PhD thesis
[20] Guth, Larry; Hawk Katz, Nets, On the Erdős distinct distances problem in the plane, Ann. of Math., 181, 1, 155-190, (2015) · Zbl 1310.52019
[21] Hansen, Pierre; Mélot, Hadrien, Variable neighborhood search for extremal graphs 9: bounding the irregularity of a graph, (2002), Groupe d’études et de recherche en analyse des décisions Montréal · Zbl 1095.05019
[22] Hoffman, Alan J., On eigenvalues and colorings of graphs, (Graph Theory and its Applications, Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969, (1970), Academic Press New York) · Zbl 0221.05061
[23] Lubotzky, Alexander; Phillips, Ralph; Sarnak, Peter, Ramanujan graphs, Combinatorica, 8, 3, 261-277, (1988) · Zbl 0661.05035
[24] Murty, M. Ram, Ramanujan graphs, J. Ramanujan Math. Soc., 18, 1, 33-52, (2003) · Zbl 1038.05038
[25] Nikiforov, Vladimir, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput., 11, 02, 179-189, (2002) · Zbl 1005.05029
[26] Nikiforov, Vladimir, Eigenvalues and degree deviation in graphs, Linear Algebra Appl., 414, 1, 347-360, (2006) · Zbl 1092.05046
[27] Nikiforov, Vladimir, A spectral Erdős-stone-Bollobás theorem, Combin. Probab. Comput., 18, 03, 455-458, (2009) · Zbl 1208.05077
[28] Nikiforov, Vladimir, A contribution to the zarankiewicz problem, Linear Algebra Appl., 432, 6, 1405-1411, (2010) · Zbl 1192.05089
[29] Nikiforov, Vladimir, Some new results in extremal graph theory, (Surveys in Combinatorics, (2011), Cambridge University Press), 213-218 · Zbl 1244.05125
[30] Nilli, A., On the second eigenvalue of a graph, Discrete Math., 91, 2, 207-210, (1991) · Zbl 0771.05064
[31] Rowlinson, Peter, On the index of certain outerplanar graphs, Ars Combin., 29, 221-225, (1990) · Zbl 0716.05016
[32] Schwenk, Allen J.; Wilson, Robin J., On the eigenvalues of a graph, (Beineke, Lowell W.; Wilson, Robin J., Selected Topics in Graph Theory, (1978), Academic Press London), 307-336, chapter 11 · Zbl 0497.05040
[33] Stanley, Richard P., A bound on the spectral radius of graphs with e edges, Linear Algebra Appl., 87, 267-269, (1987) · Zbl 0617.05045
[34] Tait, Michael; Tobin, Josh, Characterizing graphs of maximum principal ratio, (2015), preprint · Zbl 1390.05138
[35] Turán, Paul, On an extremal problem in graph theory, Mat. Fiz. Lapok, 48, 137, 436-452, (1941)
[36] Wilf, Herbert S., Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory Ser. B, 40, 1, 113-117, (1986) · Zbl 0598.05047
[37] Yuan, Hong, A bound on the spectral radius of graphs, Linear Algebra Appl., 108, 135-139, (1988) · Zbl 0655.05047
[38] Yuan, Hong, On the spectral radius and the genus of graphs, J. Combin. Theory Ser. B, 65, 2, 262-268, (1995) · Zbl 0921.05044
[39] Yuan, Hong, Upper bounds of the spectral radius of graphs in terms of genus, J. Combin. Theory Ser. B, 74, 2, 153-159, (1998) · Zbl 1028.05067
[40] Zhou, Jian; Lin, Cuiqin; Hu, Guanzhang, Spectral radius of Hamiltonian planar graphs and outerplanar graphs, Tsinghua Sci. Technol., 6, 4, 350-354, (2001) · Zbl 1003.05074
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.