Degree-Similar Graphs and Cospectral Graphs - Fan, Yi-Zheng; Xing, Ruo-Jie; Zhang, Yi-Liu; Wang, Wei (The Electronic Journal of Combinatorics, 2026)
Let G be a graph with adjacency matrix A(G) and degree matrix D(G), and let L_μ(G):=A(G)-μ D(G). Two graphs G_1 and G_2 are called degree-similar if there exists an invertible matrix M such that M^-1 A(G_1) M =A(G_2) and M^-1 D(G_1) M =D(G_2). In this paper, we address three problems concerning degree-similar graphs proposed by Godsil and Sun. First, we present a new characterization of degree-similar graphs using degree partition, from which we derive methods and examples for constructing cospectral graphs and degree-similar graphs. Second, we construct infinite pairs of non-degree-similar trees G_1 and G_2 such that tI- L_μ(G_1) and tI-L_μ(G_2) have the same Smith normal form over Q (μ)[t], which provides a negative answer to a problem posed by Godsil and Sun. Third, we establish several invariants of degree-similar graphs and obtain results on unicyclic graphs that are degree-similar determined. Lastly we prove that for a strongly regular graph G and any two edges e and f of G, G e and G f have identical μ-polynomial, i.e., (tI-L_μ(G e))=(tI-L_μ(G f)), which enables the construction of pairs of non-isomorphic graphs with same μ-polynomial, where G e denotes the graph obtained from G by deleting the edge e.