A characterization of generalized cospectrality of rooted graphs with applications in graph reconstruction

2024/08/05 by Wei Wang, Wang, Wei, Wenqiang Wen +3 · 1 citation
Computer Science · #05C50 #Combinatorics (math.CO) #Data Visualization and Analytics #FOS: Mathematics #Graph Theory and Algorithms #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2408.02488

openalex publication_date 2024/08/05 · openalex created_date 2024/10/14 · openalex updated_date 2026/07/28

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. In particular, we show that a graph with at least three vertices is reconstructible if there exists a vertex-deleted subgraph that is almost controllable and has a nontrivial automorphism.

Cited by

• On a generalization of the Johnson-Newman theorem to multiple rank-one perturbations

Related

• Characterizing cospectral vertices via isospectral reduction
• New arithmetic invariants for cospectral graphs
• Spectral characterizations of almost complete graphs
• Cospectral lifts of graphs
• Generalized Spectral Characterization of Graphs: Revisited