Degree-similar graphs

Chris Godsil ; Wanting Sun

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

The degree matrix of a graph is the diagonal matrix with diagonal entries equal to the degrees of the vertices of $X$. If $X_1$ and $X_2$ are graphs with respective adjacency matrices $A_1$ and $A_2$ and degree matrices $D_1$ and $D_2$, we say that $X_1$ and $X_2$ are \textsl{degree similar} if there is an invertible real matrix $M$ such that $M^{-1}A_1M=A_2$ and $M^{-1}D_1M=D_2$. If graphs $X_1$ and $X_2$ are degree similar, then their adjacency matrices, Laplacian matrices, unsigned Laplacian matrices and normalized Laplacian matrices are similar. We first show that the converse is not true. Then, we provide a number of constructions of degree-similar graphs. Finally, we show that the matrices $A_1-\mu D_1$ and $A_2-\mu D_2$ are similar over the field of rational functions $\mathbb{Q}(\mu)$ if and only if the Smith normal forms of the matrices $tI-(A_1-\mu D_1)$ and $tI-(A_2-\mu D_2)$ are equal.

Détail

DOI : 10.37236/13199

Classification : 05C50, 05C07
Mots-clés : degree matrix, degree similar graphs