Generalized spectral closedness of $\mathcal{F}$-free graph classes

Abstract

In this paper, we investigate the generalized spectral closedness of graph classes defined by a family $\mathcal{F}$ of forbidden induced subgraphs. To systematically study this property, we introduce a novel combinatorial concept of patterned closed walks (or ${\hat{I}}^2$-closed walks), which naturally interlaces the edges of a graph with those of its complement. By establishing the induced-subgraph expansion of these ${\hat{I}}^2$-closed walk counts, we obtain an algebraic sufficient condition for generalized spectral closedness based on the existence of a walk-realizable $\mathcal{F}$-supporter. Crucially, the search for such a walk-realizable supporter is reduced to a linear programming feasibility problem. As primary applications of this computational framework, we prove that the classes of threshold graphs and chain graphs are generalized spectrally closed.

16 pages, 4 figures, 5 tables