Multiplicity of the second-largest eigenvalue of a planar graph

作者：Chen, Guantao; Hao, Yanli^*

来源：Journal of Graph Theory, 2021, 98(3): 445-459.

DOI：10.1002/jgt.22708

• adjacency matrix
• eigenvalue
• outerplanar graph
• planar graph
• tutte decomposition

The multiplicity of the second-largest eigenvalue of the adjacency matrix A ( G ) of a connected graph G, denoted by m ( lambda 2 , G ), is the number of times of the second-largest eigenvalue of A ( G ) appears. In 2019, Jiang, Tidor, Yao, Zhang, and Zhao gave an upper bound on m ( lambda 2 , G ) for graphs G with bounded degrees, and applied it to solve a longstanding problem on equiangular lines. In this paper, we show that if G is a 3-connected planar graph or 2-connected outerplanar graph, then m ( lambda 2 , G ) <= delta ( G ), where delta ( G ) is the minimum degree of G. We further prove that if G is a connected planar graph, then m ( lambda 2 , G ) <= Delta ( G ); if G is a connected outerplanar graph, then m ( lambda 2 , G ) <= max { 2 , Delta ( G ) - 1 }, where Delta ( G ) is the maximum degree of G. Moreover, these two upper bounds for connected planar graphs and outerplanar graphs, respectively, are best possible.