Cospectral Bipartite Graphs with the Same Degree Sequences but with Different Number of Large Cycles
share
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 [ IEEE Trans. Inform. Theory 64(10):6526--6535, 2018]. This result was subsequently extended in [ IEEE Trans. Inform. Theory, accepted for publication, Dec. 2018] 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.
READ FULL TEXT