Constructions of almost controllable graphs determined by their generalized spectra

Abstract

Identifying and constructing graphs that are determined by their generalized spectrum (DGS) is a significant and challenging problem in spectral graph theory. Recently, a simple criterion for almost controllable graphs to be DGS was proposed by Lin et al. (2026), utilizing the modified walk matrix. In this paper, we investigate the evolution of the modified walk matrix under disjoint union and join operations with a singleton vertex. We establish an exact algebraic identity for the determinant of the modified walk matrix of the resulting graph. Based on this identity and the DGS-criterion of Lin et al., we construct infinite families of almost controllable graphs that are DGS, extending the previous construction of Liu et al. (2019), which was restricted to controllable graphs.

12 pages