Counting short cycles of (c,d)-regular bipartite graphs

DOI10.1142/S1793830921500221MaRDI QIDQ5013469zbMATH OpenOpenAlexFDO

Authors Mohsen Alinejad, K. Khashyarmanesh

Publication date 30 November 2021

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

(c, d)-regular graphsbipartite graphclosed walkscycle-free walks

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: Recently, working on the Tanner graph which represents a low density parity check (LDPC) code becomes an interesting research subject. Finding the number of short cycles of Tanner graphs motivated Blake and Lin to investigate the multiplicity of cycles of length girth in bi-regular bipartite graphs, by using the spectrum and degree distribution of the graph. Although there were many algorithms to find the number of cycles, they preferred to investigate in a computational way. Dehghan and Banihashemi counted the number of cycles of length $g+2$ and $g+4,$ where $G$ is a bi-regular bipartite graph and $g$ is the length of the girth $G.$ But they just proposed a descriptive technique to compute the multiplicity of cycles of length less than $2g$ for bi-regular bipartite graphs. In this paper, we find the number of cycles of length less than $2g$ by using spectrum and degree distribution of a bi-regular bipartite graph such that the formula depends only on the partitions of positive integers and the number of closed cycle-free walks from a vertex of the bi-regular bipartite graph.

Recommendations

• On computing the multiplicity of cycles in bipartite graphs using the degree distribution and the spectrum of the graph
• Cospectral bipartite graphs with the same degree sequences but with different number of large cycles
• An algorithm for counting short cycles in bipartite graphs
• Short cycles in random regular graphs
• Minimum fundamental cycle basis of some bipartite graphs

Cites work

• A recursive approach to low complexity codes
• An algorithm for counting short cycles in bipartite graphs
• An introduction to the theory of graph spectra
• Design of capacity-approaching irregular low-density parity-check codes
• On computing the multiplicity of cycles in bipartite graphs using the degree distribution and the spectrum of the graph
• On Short Cycle Enumeration in Biregular Bipartite Graphs
• 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
• Searching for Voltage Graph-Based LDPC Tailbiting Codes With Large Girth
• The Parameterized Complexity of Counting Problems

Cited in

(5)

• Cospectral bipartite graphs with the same degree sequences but with different number of large cycles
• An algorithm for counting short cycles in bipartite graphs
• On computing the multiplicity of cycles in bipartite graphs using the degree distribution and the spectrum of the graph
• Near regular LDPC codes based on combinatorial designs
• Some combinatorial applications of tactical decomposable rectangular designs families

This page was built for publication: Counting short cycles of \((c,d)\)-regular bipartite graphs

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