Cospectral Bipartite Graphs with the Same Degree Sequences but with Different Number of Large Cycles

Finding the multiplicity of cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. Recently, Blake and Lin computed the number of shortest cycles (g-cycles, where g is the girth of the graph) in a bi-regular bipartite graph, in terms of the degree sequences and the spectrum (eigenvalues of the adjacency matrix) of the graph (Blake and Lin in IEEE Trans Inf Theory 64(10): 6526-6535, 2018). This result was subsequently extended in Dehghan and Banihashemi (IEEE Trans Inf Theory 65(6):3778-3789, 2019) to cycles of length g+2,...,2g-2, in bi-regular bipartite graphs, as well as 4-cycles and 6-cycles in irregular and half-regular bipartite graphs, with g >= 4 and g >= 6, respectively. In this paper, we complement these positive results with negative results demonstrating that the information of the degree sequences and the spectrum of a bipartite graph is, in general, insufficient to count (a) the i-cycles, i >= 2g, in bi-regular graphs, (b) the i-cycles for any i>g, regardless of the value of g, and g-cycles for g >= 6, in irregular graphs, and (c) the i-cycles for any i>g, regardless of the value of g, and g-cycles for g >= 8, in half-regular graphs. To obtain these results, we construct counter-examples using the Godsil-McKay switching.