Locating eigenvalues of matrogenic graphs in linear time
A graph \(G = (V, E)\) is defined as matrogenic if \((V, \mathcal{I}_{V} )\) is a matroid, where \(\mathcal{I}_{V}\) denotes the family of all vertex sets that induce a threshold graph. Using a decomposition due to \textit{R. I. Tyshkevich} [Discrete Math. 51, 91--100 (1984; Zbl 0545.05055)], the authors prove that matrogenic graphs have clique-width at most 4, and this allows them to compute, in linear time, some spectral parameters, such as the spectral radius and the algebraic connectivity, for subfamilies of these graphs. This is achieved using the diagonalize algorithm developed by \textit{M. Fürer} et al. [Linear Algebra Appl. 560, 56--85 (2019; Zbl 1402.05136)]. The techniques applied here may provide valuable tools to further explore spectral properties of matrogenic graphs and related graph classes as well. Two conjectures conclude the paper.
- Degree sequences of matrogenic graphs
- Eigenvalue location in cographs
- Eigenvalue location in graphs of small clique-width
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3674138 (Why is no real title available?)
- scientific article; zbMATH DE number 3613062 (Why is no real title available?)
- Locating eigenvalues in graphs. Algorithms and applications
- Locating the eigenvalues of trees
- Matroids arisen from matrogenic graphs
- Old and new results on algebraic connectivity of graphs
- Once more on matrogenic graphs
- Systems analysis by graphs and matroids. Structural solvability and controllability
- Threshold graphs and related topics
- Upper bounds to the clique width of graphs
This page was built for publication: Locating eigenvalues of matrogenic graphs in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6885580)
