Name
Abstract | ||
|---|---|---|
Given a bipartite graph G=(V,E) with bipartition V=A∪B, where |A|=|B|. We present a new construction of pairs of cospectral bipartite graphs by “rotating” G in two different ways. More precisely, let l and k be two positive integers with l≠k. Take l copies of A (resp. B) and k copies of B (resp. A), say A1,A2,…,Al and B1,B2,…,Bk (resp. B1′,B2′,…,Bl′ and A1′,A2′,…,Ak′). Let Γ (resp. Γ′) be the graph with vertex set V(Γ)=A1∪A2∪⋯∪Al∪B1∪B2∪⋯∪Bk (resp. V(Γ′)=B1′∪B2′∪⋯∪Bl′∪A1′∪A2′∪⋯∪Ak′), such that the vertices of Γ (resp. Γ′) are adjacent if and only if they are adjacent in G. We show that Γ and Γ′ are cospectral with respect to the adjacency matrix, as well as the normalized Laplacian matrix. Moreover, we give a simple necessary and sufficient condition for Γ and Γ′ to be non-isomorphic. The main ingredient of the proof involves a use of Hall’s Marriage Theorem. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.disc.2020.112020 | Discrete Mathematics |
Keywords | DocType | Volume |
Graph spectra,Cospectral graphs,Hall’s Marriage Theorem | Journal | 343 |
Issue | ISSN | Citations |
10 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yizhe Ji | 1 | 0 | 0.34 |
| Shicai Gong | 2 | 0 | 0.34 |
| Wei Wang | 3 | 81 | 12.64 |