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

DOI10.1007/S00373-019-02110-6MaRDI QIDQ2287757zbMATH OpenOpenAlexWikidataFDO

Authors A. Dehghan, Amir H. Banihashemi

Publication date 21 January 2020

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

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

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)

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.

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)\)

Cites work

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

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)