A Characterization of Generalized Cospectrality of Rooted Graphs with Applications in Graph Reconstruction

Abstract

Extending a classic result of Johnson and Newman, this paper provides a matrix characterization for two generalized cospectral graphs with a pair of generalized cospectral vertex-deleted subgraphs. As an application, we present a new condition for the reconstructibility of a graph. Namely, if a vertex-deleted subgraph $G-v$ of $G$ is almost controllable, then the graph $G$ is reconstructible if $G-v$ either has a nontrivial automorphism group,  or is asymmetric with a specific property.