Title: On short cycle enumeration in biregular bipartite graphs,
Abstract: A number of recent works have used a variety of combinatorial constructions
to derive Tanner graphs for LDPC codes and some of these have been shown to
perform well in terms of their probability of error curves and error floors.
Such graphs are bipartite and many of these constructions yield biregular
graphs where the degree of left vertices is a constant $c+1$ and that of the
right vertices is a constant $d+1$. Such graphs are termed $(c+1,d+1)$
biregular bipartite graphs here. One property of interest in such work is the
girth of the graph and the number of short cycles in the graph, cycles of
length either the girth or slightly larger. Such numbers have been shown to be
related to the error floor of the probability of error curve of the related
LDPC code. Using known results of graph theory, it is shown how the girth and
the number of cycles of length equal to the girth may be computed for these
$(c+1,d+1)$ biregular bipartite graphs knowing only the parameters $c$ and $d$
and the numbers of left and right vertices. While numerous algorithms to
determine the number of short cycles in arbitrary graphs exist, the reduction
of the problem from an algorithm to a computation for these biregular bipartite
graphs is of interest.