The multiplicities of eigenvalues of a graph

作者：

Highlights：

• A graph is minimal if e(G) = d + 1. The topic of characterizing all minimal graphs was initiated by Beezer [R.A. Beezer, Trees with Very Few eigenvalues, J. Graph Theory 14(4) (1990) 509–517]. We characterized all minimal caterpillars, which extends a result by Beezer. We further characterized all extremal graphs with η(G) = n−d. In fact, such work completes the first progress to determine all minimal graphs, i.e., a subclass of minimal graphs has been determined.

• A main tool used in this paper is star complement technique, which simplifies the proofs a lot.

摘要

•A graph is minimal if e(G) = d + 1. The topic of characterizing all minimal graphs was initiated by Beezer [R.A. Beezer, Trees with Very Few eigenvalues, J. Graph Theory 14(4) (1990) 509–517]. We characterized all minimal caterpillars, which extends a result by Beezer. We further characterized all extremal graphs with η(G) = n−d. In fact, such work completes the first progress to determine all minimal graphs, i.e., a subclass of minimal graphs has been determined.•A main tool used in this paper is star complement technique, which simplifies the proofs a lot.

论文关键词：Graphs,Eigenvalues,Multiplicities

论文评审过程：Received 18 November 2021, Revised 12 January 2022, Accepted 16 January 2022, Available online 26 January 2022, Version of Record 26 January 2022.

论文官网地址：https://doi.org/10.1016/j.amc.2022.126957