Locating eigenvalues of unicyclic graphs. (English) Zbl 1499.05352
Summary: We present a linear time algorithm that computes the number of eigenvalues of a unicyclic graph in a given real interval. It operates directly on the graph, so that the matrix is not needed explicitly. The algorithm is applied to study the multiplicities of eigenvalues of closed caterpillars, obtain the spectrum of balanced closed caterpillars and give sufficient conditions for these graphs to be non-integral. We also use our method to study the distribution of eigenvalues of unicyclic graphs formed by adding a fixed number of copies of a path to each node in a cycle. We show that they are not integral graphs.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
References:
| [1] | K. Balińska, D. Cvetković, Z. Radosavljević, S. Simić, D. Stevanović: A survey on integral graphs. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 13 (2002), 42-65. · Zbl 1051.05057 |
| [2] | S. Barik, S. Pati, B. K. Sarma: The spectrum of the corona of two graphs. SIAM J. Discrete Math., 21 (1) (2007), 47-56. · Zbl 1138.05046 |
| [3] | R. O. Braga, V. M. Rodrigues, V. Trevisan: On the distribution of Laplacian eigenvalues of trees. Discrete Math., 313 (2013), 2382-2389. · Zbl 1279.05045 |
| [4] | R. O. Braga, R. R. Del-Vecchio, V. M. Rodrigues, V. Trevisan: Trees with 4 or 5 distinct normalized Laplacian eigenvalues. Linear Algebra Appl., 471 (2015), 615-635. · Zbl 1307.05137 |
| [5] | F. R. K. Chung: Spectral Graph Theory. CBMS Reg. Conf. Ser. Math., Vol. 92, Amer. Math. Soc., Providence, RI, 1997. · Zbl 0867.05046 |
| [6] | E. Fritscher, C. Hoppen, I. Rocha, V. Trevisan: On the sum of the laplacian eigenvalues of a tree. Linear Algebra Appl., 435 (2011), 371-399. · Zbl 1226.05154 |
| [7] | R. Horn, C. R. Johnson: Matrix Analysis. Cambridge University Press, 1985. · Zbl 0576.15001 |
| [8] | S. Hu: The largest eigenvalue of unicyclic graphs. Discrete Math., 307 (2007), 280-284. · Zbl 1116.05050 |
| [9] | D. P. Jacobs, V. Trevisan: Locating the eigenvalues of trees. Linear Algebra Appl., 434 (1) (2011), 81-88. · Zbl 1231.05167 |
| [10] | G. R. Omidi: On Integral Graphs with Few Cycles. Graphs Combin., 25 (2009), 841-849. · Zbl 1205.05150 |
| [11] | S. Radenković, I. Gutman: Total pi-electron energy and Laplacian energy: how far the analogy goes? J. Serb. Chem. Soc., 72 (12) (2007), 1343-1350. |
| [12] | Rodrigo O. Braga (Received 08.10.2016.) |
| [13] | Instituto de Matemática, (Revised 19.10.2017.) |
| [14] | Virgínia M. Rodrigues Instituto de Matemática, Universidade Federal do Rio Grande do Sul, Bento Gonçalves 9500 Porto Alegre, Brazil E-mail: vrodrig@mat.ufrgs |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
