Degree-Similar Graphs and Cospectral Graphs
The Electronic Journal of Combinatorics · 19.06.2026 · 33 (2)
DOI: 10.37236/14707 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 19.06.2026. Verfasst von Yi-Zheng Fan und 3 weiteren Autor:innen.
Abstract (Originalsprache)
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$.
Zitieren
APA
Fan, Y., Xing, R., Zhang, Y., & Wang, W. (2026). Degree-Similar Graphs and Cospectral Graphs. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/14707
Vancouver
Fan Y, Xing R, Zhang Y, Wang W. Degree-Similar Graphs and Cospectral Graphs. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/14707
BibTeX
@article{Fan2026,
author = {Fan, Yi-Zheng and Xing, Ruo-Jie and Zhang, Yi-Liu and Wang, Wei},
title = {Degree-Similar Graphs and Cospectral Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {2},
doi = {10.37236/14707}
}
EUVIMED