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 , … , 2 g- 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≥ 2 g, 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