Locating eigenvalues of matrogenic graphs in linear time (Q6885580)

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.