Cospectral bipartite graphs with the same degree sequences but with different number of large cycles

DOI10.1007/S00373-019-02110-6zbMATH Open1431.05099arXiv1905.13228OpenAlexW2981974404WikidataQ126991793 ScholiaQ126991793MaRDI QIDQ2287757FDOQ2287757

Authors: A. Dehghan, Amir H. Banihashemi 

Publication date: 21 January 2020

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: 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 [{em IEEE Trans. Inform. Theory 64(10):6526--6535, 2018}]. This result was subsequently extended in [{em IEEE Trans. Inform. Theory, accepted for publication, Dec. 2018}] to cycles of length $g+2,ldots,2g-2$, in bi-regular bipartite graphs, as well as $4$-cycles and $6$-cycles in irregular and half-regular bipartite graphs, with $ggeq4$ and $ggeq6$, 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, $igeq2g$, in bi-regular graphs, (b) the $i$-cycles for any $i>g$, regardless of the value of $g$, and $g$-cycles for $ggeq6$, in irregular graphs, and (c) the $i$-cycles for any $i>g$, regardless of the value of $g$, and $g$-cycles for $ggeq8$, in half-regular graphs. To obtain these results, we construct counter-examples using the Godsil-McKay switching.

Full work available at URL: https://arxiv.org/abs/1905.13228

Recommendations

• On computing the multiplicity of cycles in bipartite graphs using the degree distribution and the spectrum of the graph
• Counting short cycles of \((c,d)\)-regular bipartite graphs
• Bipartite graphs \(K_{n,n+r}-A(|A|\leq 3)\) determined by their cycle length distributions
• On the construction of cospectral nonisomorphic bipartite graphs
• On the girth cycles of the bipartite graph \(D(k, q)\)

zbMATH Keywords

graph spectrumgirthbipartite graphscycle multiplicityTanner graphsbi-regular bipartite graphsdegree sequences of a graphGodsil McKay switchinghalf-regular bipartite graphsirregular bipartite graphslow-density parity-check (LDPC) codes

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex degrees (05C07) Distance in graphs (05C12) Enumeration in graph theory (05C30) Paths and cycles (05C38) Theory of error-correcting codes and error-detecting codes (94B99)

Cites Work

• Which graphs are determined by their spectrum?
• Constructing cospectral graphs
• Graph theory with applications
• Title not available (Why is that?)
• An algorithm for counting short cycles in bipartite graphs
• On integral graphs with few cycles
• HAMILTONian circuits in chordal bipartite graphs
• Factor graphs and the sum-product algorithm
• The capacity of low-density parity-check codes under message-passing decoding
• A recursive approach to low complexity codes
• Regular and irregular progressive edge-growth tanner graphs
• Eigenvalues and perfect matchings
• Regular graphs, eigenvalues and regular factors
• Cospectral regular graphs with and without a perfect matching
• Godsil-McKay switching and isomorphism
• Two spectral characterizations of regular, bipartite graphs with five eigenvalues
• Lowering the Error Floor of LDPC Codes Using Cyclic Liftings
• On the Girth of Quasi-Cyclic Protograph LDPC Codes
• Godsil-McKay switching and twisted Grassmann graphs
• Switched graphs of some strongly regular graphs related to the symplectic graph
• Which cospectral graphs have same degree sequences
• On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes
• Constructing cospectral graphs via a new form of graph product
• On the Tanner Graph Cycle Distribution of Random LDPC, Random Protograph-Based LDPC, and Random Quasi-Cyclic LDPC Code Ensembles
• New Characterization and Efficient Exhaustive Search Algorithm for Leafless Elementary Trapping Sets of Variable-Regular LDPC Codes
• Efficient Algorithm for Finding Dominant Trapping Sets of LDPC Codes
• On Short Cycle Enumeration in Biregular Bipartite Graphs
• On computing the multiplicity of cycles in bipartite graphs using the degree distribution and the spectrum of the graph
• New Sequences of Capacity Achieving LDPC Code Ensembles Over the Binary Erasure Channel
• Characterization of Elementary Trapping Sets in Irregular LDPC Codes and the Corresponding Efficient Exhaustive Search Algorithms

Cited In (3)

• On adjacency and Laplacian cospectral non-isomorphic signed graphs
• On computing the multiplicity of cycles in bipartite graphs using the degree distribution and the spectrum of the graph
• Counting short cycles of \((c,d)\)-regular bipartite graphs

This page was built for publication: Cospectral bipartite graphs with the same degree sequences but with different number of large cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2287757)