Short note on the minimum number of distinct eigenvalues of unicyclic graphs
DOI:
https://doi.org/10.5540/03.2025.011.01.0476Palabras clave:
Symmetric Matrix, Eigenvalue Multiplicity, Unicyclic GraphResumen
Let q(G) be the minimum number of distinct eigenvalues taken over all real symmetric matrices whose underlying graph is G. Using a linear time algorithm that diagonalizes any symmetric matrix associated to a unicyclic graph, we investigate the maximum eigenvalue multiplicity for these graphs. As an application, we determine the value of q(G) for some family of tadpole graphs, which are unicyclic graphs formed by adding an edge between a cycle and a path.
Descargas
Citas
B. Ahmadi, F. Alinaghipour, M. Cavers, S. Fallat, K. Meagher, and S. Nasserasr. “Minimum number of distinct eigenvalues of graphs”. In: ELA. The Electronic Journal of Linear Algebra [electronic only] 26 (Apr. 2013), pp. 673–691. doi: 10.13001/1081-3810.1679.
L. E. Allem, R. O. Braga, C. Hoppen, E. R. Oliveira, L. S. Sibemberg, and V. Trevisan. “Diminimal families of arbitrary diameter”. In: Linear Algebra and its Applications 676 (2023), pp. 318–351. issn: 0024-3795. doi: https://doi.org/10.1016/j.laa.2023.07.018.
W. Barrett, S. Butler, S. M. Fallat, H. T. Hall, L. Hogben, J. C.-H. Lin, B. L. Shader, and M. Young. “The inverse eigenvalue problem of a graph: Multiplicities and minors”. In: Journal of Combinatorial Theory, Series B 142 (2020), pp. 276–306. issn: 0095-8956. doi: 10.1016/j.jctb.2019.10.005.
W. Barrett, S. Fallat, H. T. Hall, L. Hodgen, J. C.-H. Lin, and B. L. Shader. “Generalizations of the Strong Arnold Property and the Minimum Number of Distinct Eigenvalues of a Graph”. In: The Electronic Journal of Combinatorics 24 (2017), pp. 1–28. doi: https://doi.org/10.37236/5725.
R. O. Braga, V. M. Rodrigues, and R. Silva. “Locating Eigenvalues of a Symmetric Matrix whose Graph is Unicyclic”. In: Trends in Computational and Applied Mathematics 22.4 (2021), pp. 659–674. issn: 2676-0029. doi: 10.5540/tcam.2021.022.04.00659.
W. E. Ferguson. “The Construction of Jacobi and Periodic Jacobi Matrices With Prescribed Spectra”. In: Mathematics of Computation 35.152 (1980), pp. 1203–1220. issn: 00255718, 10886842.
R. Fernandes and C. M. da Fonseca. “The inverse eigenvalue problem for Hermitian matrices whose graphs are cycles”. In: Linear and Multilinear Algebra 57.7 (2009), pp. 673–682. doi: 10.1080/03081080802187870.
C. M. da Fonseca. “A lower bound for the number of distinct eigenvalues of some real symmetric matrices”. In: ELA. The Electronic Journal of Linear Algebra [electronic only] 21 (2010), 3–11. issn: 1081-3810.
L. J. Gray and D. G. Wilson. “Construction of a Jacobi matrix from spectral data”. In: Linear Algebra and its Applications 14.2 (1976), pp. 131–134. issn: 0024-3795. doi: https://doi.org/10.1016/0024-3795(76)90020-3.
L. Hogben. “Spectral graph theory and the inverse eigenvalue problem of a graph.” In: ELA. The Electronic Journal of Linear Algebra [electronic only] 14 (2005), pp. 12–31.
R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1990. isbn: 0521386322.
A. Leal-Duarte and C. R Johnson. “On the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a given tree”. In: Mathematical Inequalities and Applications 5 (2002), pp. 175–180. doi: 10.7153/MIA-05-19.
