Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2302.03854 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916582131761152 |
|---|---|
| author | Godsil, Chris Sun, Wanting Zhang, Xiaohong |
| author_facet | Godsil, Chris Sun, Wanting Zhang, Xiaohong |
| contents | Let $M\circ N$ denote the Schur product of two matrices $M$ and $N$. A graph $X$ with adjacency matrix $A$ is walk regular if $A^k\circ I$ is a constant times $I$ for each $k\ge0$, and $X$ is 1-walk-regular if it is walk regular and $A^k\circ A$ is a constant times $A$ for each $k\ge0$. Assume $X$ is 1-walk regular. Here we show that by deleting an edge in $X$, or deleting edges of a graph inside a clique of $X$, we obtain families of graphs that are not necessarily isomorphic, but are cospectral with respect to four types of matrices: the adjacency matrix, Laplacian matrix, unsigned Laplacian matrix, and normalized Laplacian matrix. Furthermore, we show that removing edges of Laplacian cospectral graphs in cliques of a 1-walk regular graph results in Laplacian cospectral graphs; removing edges of unsigned Laplacian cospectral graphs whose complements are also cospectral with respect to the unsigned Laplacian in cliques of a 1-walk regular graph results in unsigned Laplacian cospectral graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_03854 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cospectral graphs obtained by edge deletion Godsil, Chris Sun, Wanting Zhang, Xiaohong Combinatorics 05C50 Let $M\circ N$ denote the Schur product of two matrices $M$ and $N$. A graph $X$ with adjacency matrix $A$ is walk regular if $A^k\circ I$ is a constant times $I$ for each $k\ge0$, and $X$ is 1-walk-regular if it is walk regular and $A^k\circ A$ is a constant times $A$ for each $k\ge0$. Assume $X$ is 1-walk regular. Here we show that by deleting an edge in $X$, or deleting edges of a graph inside a clique of $X$, we obtain families of graphs that are not necessarily isomorphic, but are cospectral with respect to four types of matrices: the adjacency matrix, Laplacian matrix, unsigned Laplacian matrix, and normalized Laplacian matrix. Furthermore, we show that removing edges of Laplacian cospectral graphs in cliques of a 1-walk regular graph results in Laplacian cospectral graphs; removing edges of unsigned Laplacian cospectral graphs whose complements are also cospectral with respect to the unsigned Laplacian in cliques of a 1-walk regular graph results in unsigned Laplacian cospectral graphs. |
| title | Cospectral graphs obtained by edge deletion |
| topic | Combinatorics 05C50 |
| url | https://arxiv.org/abs/2302.03854 |