Constructing cospectral graphs via a new form of graph product. Issue 9 (2nd September 2018)

• Record Type: Journal Article
• Authors: Langberg, Michael; Vilenchik, Dan
• Is Part Of: Linear & multilinear algebra. Volume 66:Issue 9(2018)
• Page Start: 1838
• Page End: 1852
• Publication Date: 2018-09-02
• Subjects: Cospectral graphs -- graph product; 05C50 -- 05C76; Algebras, Linear -- Periodicals; Multilinear algebra -- Periodicals; 512.505
• DOI: 10.1080/03081087.2017.1373733
• Languages: English
• ISSNs: 0308-1087

Abstract

Abstract: We present a new method to construct a family of co-spectral graphs. Our method is based on a new type of graph product that we define, the bipartite graph product, which may be of self-interest. Our method is different from existing techniques in the sense that it is not based on a sequence of local graph operations (e.g. Godsil–McKay switching). The explicit nature of our construction allows us, for example, to construct an infinite family of cospectral graphs and provide an easy proof of non-isomorphism. We are also able to characterize fully the spectrum of the cospectral graphs.