Degree-Similar Graphs and Cospectral Graphs

Abstract

Let $G$ be a graph with adjacency matrix $A(G)$ and degree matrix $D(G)$, and let $L_\mu(G):=A(G)-\mu 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_\mu(G_1)$ and $tI-L_\mu(G_2)$ have the same Smith normal form over ${\mathbb{Q}}(\mu)[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 \backslash e$ and $G \backslash f$ have identical $\mu$-polynomial, i.e., $\det(tI-L_\mu(G \backslash e))=\det(tI-L_\mu(G \backslash f))$, which enables the construction of pairs of non-isomorphic graphs with same $\mu$-polynomial, where $G \backslash e$ denotes the graph obtained from $G$ by deleting the edge $e$.