Recursive Constructions of Graphs of Large Girth and Given Degree

Abstract

This paper is devoted to recursive constructions of small regular graphs of given degree and girth , called (, )-graphs, using Cayley graphs, perfect matchings and/or voltage graph constructions. First, we consider an analog of the canonical double cover construction, which produces (, + 1)-graphs of even girth from (, )-graphs of odd girth by relying on Cayley graphs and/or voltage lifts. By considering Moore bounds, we show that there is no universal recursive construction of (, + 1)-graphs from (, )-graphs of even girth that would produce graphs whose order is a constant multiple of the order of the original graph. Further, we introduce a novel approach for obtaining ( + 1, 6)-graphs from (, 6)-graphs using perfect matchings and the voltage graph construction and compare our results with previously known results. We conclude our paper with a discussion of the potential of computer assisted searches relying on our constructions, and present a link between (, 6)-graphs and applications in communication systems.

Keywords

• Regular graphs
• girth
• voltage graph
• Cayley graph
• LDPC codes

1. Introduction

We define a (, )-graph as a -regular graph of girth . One of the fundamental problems addressed in Extremal Graph Theory is the so-called Cage Problem; the problem of finding a smallest (, )-graph for a given pair of parameters , ≥ problem over a well-defined infinite class of graphs. This problem has been widely studied since the pioneering work of Erdős and Sachs [ 7 ] and that of Hofman and Singleton [ 15 ]. The first pair of authors showed that for any given integers ≥ 3, ≥ 2, there exist infinitely many (, )-graphs [ 7 ]. However, determining a smallest (, )-graph in this infinite class has proven to be a much 3. It is a hard optimization harder problem.

In this paper, we consider recursive constructions of

two kinds, both starting from a given (, )-graph and resulting in a new larger graph. the girth , while keeping fixed. This type of construction can be traced back to the work of Erdős and Sachs [ 7 ]. Using a construction called a canonical double cover, starting from a (, )-graph of odd girth , they constructed a new graph of the same degree and higher girth, whose order is twice the order of the original graph, thereby proving the following: Theorem 1 ([ 7 ]). For any integer ≥ 3 and odd ≥ 3, (, + 1) ≤ 2(, ).

In a recent development, Balbuena et al. [2] improved this bound as expressed below.

Theorem 2 ([ 2 ]). Let ≥ 3 and ≥ 5 odd. Then, (, + 1) ≤ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ 2(, ) − 2

≡ 3 2(, ) − 4 ≡ 1 ︂( (− 1) − 3 − 2 (mod 4) ︂( 2(− 1) − 1 − 2 (mod 4).

︂) ︂) (1)

Graphs whose orders match these results are also ob

a subgraph of the original (, )-graphs). In Section 2, we illustrate the canonical double cover of graphs with examples and provide two diferent constructions, which produce the same graphs as the canonical double cover but rely on Cayley graphs and voltage lifts.

It is important to note that the canonical double cover

construction produces (, + 1)-graphs from (, )graphs of odd girth which are always twice as large as the original graph. Unfortunately, this construction gate the possibility of a recursive construction starting from a (, )-graph of even girth using the parametric

First, we attempt to increase the second parameter, tained using the canonical double cover construction (on ITAT’22: Information technologies – Applications and Theory, Septem- only works for odd girth . For this reason, we investiAttribution 4.0 International (CC BY 4.0). Authors supported in part by VEGA 1/0423/20, and of (, )-graphs: (, ) ≤ (, ), for all , ≥ 3.

APVV-19-0308.

Definition 1. For ≥ 2, ≥ 3, the Moore bound (, ) of the (, )-graph is given by

Our paper is organized as follows: Section 2 contains an explanation of the concept of voltage graph construction with examples. Section 3 contains two analogs of the canonical double cover construction starting with Cayley graphs with some examples again. In Section 4, we give a parametric analysis of the Moore bound. Our recursive construction using perfect matchings is presented in Section 5, while the comparison of our construction with existing constructions is presented in Section 6. Finally, in Sections 7 and 8 we discuss computer assisted methods and an application of (, 6)-graphs in communication systems.

Our analysis shows that there is no constant such

that for any given pair , ≥ 3, even, one could start from a (, )-graph and obtain a (, + 1)-graph whose order is at most an multiple of the order of the original graph. For more details on the Moore bounds and cages we refer the reader to the dynamic cage survey paper by Exoo and Jajcay [ 8 ]. 2. Voltage Graph Construction

Next, we try to increase the degree of the obtained graph while keeping its girth constant. In the oppo- Let Γ be a finite graph, not necessarily simple (possibly site direction, Gács and Héger in 2008 built on the work with multiple edges and loops), and (Γ) the set of darts of Brown [ 4 ] and presented recursive constructions for of Γ obtained by replacing each edge of Γ by a pair of = 6, 8, 12, which resulted in graphs of smaller degrees opposing darts (arcs) and − 1. A voltage assignment on [ 12 ]. Namely, they considered incidence graphs of gen- Γ is any mapping : (Γ) → satisfying the condition eralized -gons and obtained smaller regular subgraphs that (− 1) = ( ())− 1 for all ∈ (Γ), where is a by removing/adding some edges and vertices. To achieve group called the voltage group. For the purposes of our this, for any given generalized -gon (, ℒ), they de- construction, we will always assume that is finite. The ifned a -good structure of lines and points to delete in voltage graph (also called the derived graph or the lift) order to obtain a smaller (, )-graph of smaller degree. of Γ with respect to , denoted by Γ , is a new graph They proved the following: (1) For any prime power with vertex set (Γ ) = (Γ) × and edge set (Γ ) and 1 ≤ ≤ , there is a ( + 1 − , 6)-regular graph defined by making vertices and adjacent in Γ if whose order is 2(2 + + 1 − ( + 1)) with the size = (, ) ∈ (Γ) and = (). For any voltage of the -good structure + 1. (2) For any for which graph Γ , we define the net voltage of a walk in Γ as a projective plane exists, there exists a (, 6)-graph of the product of the group elements assigned to the edges order 2(2 − 1). (3) For any square prime power and of the walk in the corresponding order. 1 ≤ ≤ − √, there is a (, 6)-graph whose order We say that Γ˜ is a covering graph of Γ if there exists is 2(2 + + 1 − ( + √ + 1)) with the size of the a map : (Γ˜) →− (Γ) called the covering map of -good structure equal to ( + √ + 1). However, their Γ such that for every ∈ (Γ˜), the set of neighbours result is restricted to degrees which are prime powers, of denoted by Γ˜ () is mapped one-to-one onto the and the resulting graphs are of smaller degrees than the neighborhood Γ( ()). We also say that Γ˜ is a lift of starting point-line incidence graphs. To the best of our Γ if there exists a covering map from (Γ˜) to (Γ), and knowledge, until now there was no universal approach we call the lift an -lift of Γ if the preimages − 1() proceeding from an arbitrary (, 6)-graph to a ( + 1, 6)- consist of elements. Clearly, the voltage lift Γ is a graph. ||-lift of Γ.

Proceeding through the paper, we present several re- We say that Γ is a canonical double cover of Γ if the cursive constructions. Two of them are shown to be voltage group is Z2 and each edge of Γ receives the voltequivalent to the canonical double cover construction age assignment 1 ∈ Z2. This is a very special type of but rely on Cayley graphs. Another construction gives voltage graph construction, and it has been used by many (+1, 6)-graphs from (, 6)-graphs. This construction is authors [ 2, 11, 16, 19 ]. In what follows, we shall apply a new approach to obtaining (, 6)-graphs of an increas- the canonical double cover to illustrate how to obtain a ing degree with a fixed girth. Our approach makes it pos- larger graph of even girth from a graph of odd girth. sible to move from a smaller (, 6)-graph to a ( + 1, 6)- Let Γ be a graph with odd girth . Take Z2 = {0, 1} as graph. It is opposite to the construction of Gács and the voltage group and define () = 1, for all ∈ (Γ). Héger [ 12 ] which starts from a bigger (, 6)-graph and produces a smaller ( − , 6)-graph. We rely on the fact Example 1. For 4 and Pentagon, canonical double covers that every regular bipartite graph has a perfect matching are respectively given below. and voltage graph construction to construct the desired graph of higher degree.

Example 2. Let Γ be the base graph of five vertices and girth three shown in Figure 2. The canonical double cover

To this end, we see that Theorem 1 of Erdős and Sachs is a consequence of the canonical double cover construction.

In other words, the canonical double cover of a -regular graph of odd girth is a -regular graph of even girth greater than .

Next, we present two analogs of the canonical double cover construction by utilizing the idea of a Cayley graph and voltage lift.

3. Recursive Constructions from

Odd to Even Girth Starting from

Cayley Graphs

Let be a finite group with a generating set = − 1 not containing the identity and closed under inverses. The Cayley graph Γ = (, ) is a regular graph of degree || that has as its set of vertices, and its adjacency is defined by making each vertex ∈ adjacent to all the vertices in the set = { | ∈ }. Alternatively, for any two vertices , ℎ ∈ , is adjacent to ℎ if and only if ℎ− 1 ∈ . Note that the fact that is closed under inverses makes the resulting graph undirected. The graph Γ = (, ) is connected if and only if generates .

3.1. Direct Product Construction

Our first construction is essentially just another way of looking at the canonical double cover of a Cayley graph, which might sometimes prove useful. It shows that the canonical double cover of a Cayley graph is a Cayley graph again. The proof is left to the reader.

Theorem 3. Let Γ = (, ), = {1, 2, . . . , }. The Cayley graph Γ = ( × Z2, {(1, 1), (2, 1), . . . , (, 1)}) is the canonical double cover of Γ.

3.2. Dipole Lift Construction

Let (, ) be a Cayley graph. Consider the base graph Γ = (, ) which is a dipole consisting of two vertices and || multiple parallel edges. Take to be the voltage group, and let assign to each edge of Γ a unique element of . Consider the lift Γ .

Example 4. Consider a complete graph 4 which is a Cayley graph (, ) with = Z22 and = {(1, 0), (0, 1), (1, 1)}. The dipole lift graph Γ is shown in Figure 3.

Example 5. Let (, ) a be Cayley graph with = 3 and = {(12), (13), (23)}. Then, the dipole lift graph Γ is shown in Figure 4. Theorem 4. Let (, ) be a Cayley graph. The lift of the dipole graph with || parallel edges obtained via Construction 3.2 is isomorphic to the canonical double cover of (, ).

Proof. The proof is again straightforward. It is easy to see that the preimage sets { | ∈ }, { | ∈ }, of the two vertices , of the dipole (called fibers ) are independent and that the edges of the constructed graph connect to ℎ if and only ℎ = , for some ∈ .

To conclude the section, it is interesting to note that the

connectedness of the graphs constructed via Construction 3.2 is expressed diferently from that of the canonical double cover stated in Condition 3 of Lemma 1. Lemma 2. Let (, ) be a Cayley graph. The lift of the dipole graph with || parallel edges obtained via Construction 3.2 is connected if and only if the subgroup of all elements of that can be expressed as a product of elements from consisting of an even number of generators is equal to .

4. Parametric Analysis of the

Moore Bound

All the preceding constructions start with an odd-girth graph and construct an even-girth graph of larger girth and order twice the order of the original graph. In view of the usefulness of this construction, it is natural to ask whether there might exist an analogous universal construction starting from an even-girth graph and resulting in an odd-girth graph of larger girth and order an -multiple of the order of the original graph.

Here, we present a parametric analysis of the Moore bound with a view to understanding the feasibility of obtaining a recursive construction from even to odd girth. The aim is to understand the rate at which (, ) varies with a continuous change in or or both. In other words, we are looking for the best possible and for which these inequalities hold (, + 1) ≤ (, ) ( + 1, ) ≤ (, ) in case of even .

Since (, ) ≤ (, ), ∀ , ≥ 3, we approach this question by considering the Moore bound. Obtaining constants ′, ′ for which (, + 1) ≤ ′ (, ) or ( + 1, ) ≤ ′ (, ) is suficient for determining lower bounds for the rate of growth of (, ).

To analyze the parameters and , we first simplify the expression in Equation (2) by substituting the formula for the sum of the th term of the geometric progression to obtain construction from odd to even girth, and the bound This result is in line with the canonical double cover for all ≥ the lower bound: ∈ R such that (, + 1) ≤ (, ), for all ≥ 3 and all even ≥ induction would yield the upper bound: (, 2) ≤ 2− 2 − 2(, 4) = 2− 2 − 22,

3. At the same time, the above analysis yields (, 2) = ,2− 1 ,2− 2 . . . ,5 ,4(, 4) ≥ ︂( 2( − 1) multiple of the original graph. However, the precise ratio also depends on how close is the order of the smallest (, )-graph, even, to the corresponding Moore bound (, ).

5. A Recursive Construction of

( + 1, 6)-Graphs from (, 6)-Graphs Using Perfect

Matching

Our last construction is again recursive. It starts with a -regular bipartite Γ = (, ) and a selected perfect matching for Γ whose existence is guaranteed by the following well-known result.

Theorem 6 ([ 17 ]). Every regular bipartite graph has a perfect matching.

Select a perfect matching for a bipartite -regular Γ, and let Γ˜ be the multigraph obtained from Γ by adding a parallel edge to each of the edges of the perfect matching of Γ. It follows from the properties of a perfect matching that Γ˜ is a (+1)-regular multigraph. In what follows, we shall refer to the added edges of Γ˜ as the new edges and to the original edges of Γ as the old edges. To use the voltage graph construction, let us further replace each edge of Γ˜ with a pair of opposing darts. Let (Γ˜) = 1 ∪ 2 be the bipartite division of the vertices of Γ˜, and let (Γ˜) denote the set of darts of Γ˜. Let our selected voltage group be = Z3, assign the voltage 0 to all darts originating from the old edges of Γ˜ and assign the voltage 1 to either of the two darts formed from the new edges of Γ˜ (and 2 to

the opposed dart). Consider the voltage graph Γ˜ .

Lemma 3. Γ˜ is a ( + 1)-regular bipartite graph.

Proof. Let 1 and 2 be the vertex sets of Γ˜ formed as unions of fibers of the elements of 1 and 2, respectively.

The two sets are clearly disjoint, while no two vertices belonging to 1 and no two vertices belonging to 2 are adjacent. As the degree of the vertices in the voltage lift is equal to the degree of the corresponding vertices in the ( + 1)-regular base graph, the result follows.

Example 6. Let us apply the first step of the above voltage lift construction to the bipartite cubic Heawood graph of order 14. Selecting a particular perfect matching and adding the new parallel edges results in the multigraph shown in Figure 5.

The edges of Γ are of two types: the lifts of the old edges, which we shall refer to as the horizontal edges, and the lifts of the new edges, which shall be called vertical edges. Since our voltage group is Z3, and all the old edges of Γ˜ received the voltage 0 ∈ Z3, Γ˜ three parallel horizontal copies of (Γ). We call each of

contains such copy a layer. While the horizontal edges connect vertices belonging to the same layer, vertical edges connect vertices between distinct layers. If we denote the vertices of Γ by 0, 1, . . . , − 1 (with representing the order of Γ), all vertices of Γ

are of the form , , where indicates the position of the vertex in a layer and ∈ Z3 indicates the specific layer. Let us assume without loss of generality that the new edges of the perfect matching in Γ˜ connect the vertices , +1, with even.

Under these assumptions, all the vertical edges in Γ are of the form , ,+1, with even, and + 1 calculated

modulo 3. The three layers of Γ˜ , its vertical edges, and the corresponding base graph Γ˜ are pictured in Figure 6. the edges of Γ as shown in Figure 6.

Figure 6: Base graph Γ˜ and lift graph Γ˜ 4-cycle in Γ˜ . Then, can either be contained in one of the layers or contains vertices from two or contains more layers. Since each layer is a copy of Γ, which Clearly, the above upper bound is not particularly is of girth 6, no cycle fully contained in a horizontal strong. This is due to the fact that we do not know layer is of length 4. If is contained in two or more whether (, )-cages for even must necessarily be bilayers, then must be of one of the three forms partite. If that was the case, we would obtain the stronger {(, ), (+1, ), (+1,+1), (+2,+1), (, )}, or result ( + 1, ) ≤ 3(, ), for all ≥ 3 and even {(+1, ), (, ), (+1,+1), (+2,+1), (+1, )}, ≥ 4. Interestingly, the bipartiteness of the (, )-cages or {(+1, ), (, ), (+1,+1), (,+1), (+1, )}; for even has been repeatedly conjectured by various pictured in Figure 8. authors [ 8 ].

Suppose is a cycle of the first type. In this case, two Even performing a detailed analysis of the rate of incident edges (, +1) and (+1, +2) belong to the growth of the Moore bound in case of a fixed even girth perfect matching, which is a contradiction. Similarly, yields a much weaker rate of growth for (, ) than the second case implies that two edges (, +1) and the one stated in Theorem 7: (+1, +2) with a common vertex +1 are in the perfect matching, which is again impossible. The last case Case 3. Let = 2 be fixed. Define , as the following would result in forcing a cycle (− 1, , +1, +2) in ratio: the base graph. This is impossible since Γ is assumed to be of girth 6. It follows that the girth of Γ˜ is indeed 6.

Example 7. Consider the graph in Figure 5 obtained from Heawood graph. Applying Lemma 4 yields the graph below.

Recall that Heawood graph is a bipartite 3-regular

graph of girth 6 and order 14. Note also that the graph Γ˜ constructed from a bipartite -regular graph of girth 6 is bipartite ( + 1)-regular of girth 6. Thus, relying repeatedly on Theorem 6 and starting from the Heawood graph, we obtain the following.

Theorem 7. Let ≥ 3. Then, (, 6) ≤ 3− 3 · 14. , = ( + 1, ) (, ) ≥ =

(2 − 2)( − 2) (2( − 1) − 2)( − 1)

( − 1)( − 2) (( − 1) − 1)( − 1)

Thus, regardless of the girth, lim→∞ , = 1, and unlike the case of the transition from even girth to odd, there might exist a constant and a universal construction of a ( + 1, )-graph from a (, )-graph which yields ( + 1, )-graphs of orders proportional to a multiple of the order of the original (, )-graph with smaller than 3.

6. Comparison with Existing

Constructions

In literature, one can find several constructions of ( − 1, 6)-graphs starting with a known (, 6)-graph [ 1, 2, 4, 12 ]. In this section, we compare our construction with a recursive construction for girth 6 introduced by Gács and Héger [ 12 ] which is the best recursive construction for (, 6)-graphs. Like our construction, their construction generates an infinite family of (, 6)-graphs using the idea of the -good structure. However, Gács and Héger’s construction works in a way that is opposite to ours.

Namely, it starts from a point-line incidence graph of a projective plane which is a ( + 1, 6) Moore graph of degree equal to a prime power plus 1, and recursively constructs graphs of smaller degrees by removing or adding vertices and edges (as we discussed earlier in the Introduction). As it is well known, the gap between two consecutive prime powers can be arbitrarily large.

Since the ratio of the number of prime powers to that of prime numbers converges to 1, prime powers grow asymptotically at the same rate. Thus, the orders of (, 6)graphs constructed by removing -good structures for ’s which are only slightly larger than a prime power but are quite a bit smaller than the next prime power may be cover voltage assignment clearly assigns the net voltvery far from the orders of corresponding cages. age 0 ∈ Z2 to all cycles of even length, and hence, the

In comparison, our constructions produce ( + 1, 6)- lift of an even-girth base graph is of the same girth as graphs from (, 6)-graphs for any degree . This means the original girth. This does not necessarily mean that that, especially in the case of ’s described at the end no Z2-voltage assignment for an even girth base graph of the previous paragraph, our constructions require a can lead to a lift graph of larger girth. As long as the smaller number of recursions (as we may start from the order of the lift of a (, )-graph Γ does not violate the closest smaller prime power than ). Nevertheless, our Moore bound for and ′ > , a Z2-voltage assignment construction does not outperform that of Gács and Héger, having the property that the net voltage of no -cycle and should be therefore viewed as the basis for another fu- of Γ equals 0 might exist. Obviously, any such voltage ture construction that might eventually produce smaller assignment would lead to a (, ′)-graph of twice the graphs; at least in cases of ’s just a bit larger than a order of the base graph. However, one must not forget prime power. the results of Section 4 where we proved that there must exist even girth (, )-graphs for which no Z2-voltage assignments have the above property (as otherwise there 7. Computer Assisted Methods would exist a ‘universal’ construction doubling the order and increasing the girth of all even girth graphs).

All the construction methods considered so far were de- More specifically, the results of Section 4 suggest that terministic in the somewhat loose sense that they did not in order to obtain a voltage graph lift of an even-girth require searching a large space of possible constituents. -regular graph of larger girth, one has to use voltage asIn this section, we will briefly discuss methods for im- signments using groups of orders proportional to 2 . This proving the girth of a voltage lift graph using computer suggests the following computational approach to obtainassisted searches. The key lemma we will rely on is the ing (, ′)-graphs from (, )-graphs using the voltage following: graph construction (we will assume that is even and Lemma 5. [9, Lemma 2.1.] Let Γ be a finite graph and ′ > ). : (Γ) → be a voltage assignment of Γ. The girth of Let Γ be a -regular graph of even girth , and let the voltage graph lift Γ is equal to the length of a shortest be a finite group of order close to 2 or larger. A brute closed non-backtracking walk in Γ of net voltage 1. force approach to answering the question whether there exists a voltage assignment : (Γ) → that leads to

A closed non-backtracking walk in is a closed walk a (, ′)-graph Γ of girth ′ > is to consider all poswhich does not contain an edge travelled in one direction sible -voltage assignments of Γ and for each of them to followed immediately by the same edge travelled in the test whether the net voltages of all girth cycles in Γ difer opposite direction. It is easy to see that the length of a from 1. Should one find such a voltage assignment, the closed non-backtracking walk in of girth must be at answer to the above question would be positive, otherleast , and also that a closed non-backtracking walk in wise the answer would be a no. In case of a no answer, of length must in fact be a cycle. The net voltage of one might next consider other groups of the same order a closed walk 12 . . . , ∈ () is the product of as or groups of orders larger than ||. It is useful the voltages of its darts in the order determined by the to point out that considering larger and larger groups walk, i.e., the net voltage of the above walk is the product will eventually lead to a voltage assignment for which (1) (2) . . . () ∈ . Our observations together the net voltages of all girth cycles in Γ difer from 1. with Lemma 5 yield the following corollary. An easy proof of this fact uses the voltage assignment |(Γ)| assigning to each pair of opposing Corollary 1. Let Γ be a finite graph of girth and : : (Γ) → Z2 (Γ) → be a voltage assignment for Γ. The girth of darts of Γ a diferent unit basis vector ⃗ and the fact the lift Γ is greater than the girth of Γ if and only if the that there are no repeated edges in girth cycles of Γ (and net voltage of every -cycle of Γ is diferent from 1. hence all girth cycles in Γ have a non-trivial voltage). Unfortunately, the number of possible voltage assignments

When applying the above corollary to the canonical : (Γ) → is equal to |||(Γ)|, and using brute double cover of an odd-girth base graph Γ, we quickly force becomes very quickly infeasible. observe that the net voltage of any -cycle (as well as of any odd-length cycle) in Γ is equal to 1, the non-identity element of Z2. This is the basis of the proof of Lemma 1 8. Application of (, 6)-Graphs in as well as the argument that shows that the canonical Communication Systems double cover of an odd-girth graph Γ has larger girth than Γ itself. Applying Corollary 1 to graphs of even The problem of communicating reliably over a noisy girth is quite a bit trickier. Namely, the canonical double channel has been in existence for many decades. One approach to solving this problem is using error-correcting codes. An error-correcting code (ECC) is an encoding scheme that transmits messages as binary strings, in such a way that the message can be recovered even if some bits are erroneously flipped. It is done by introducing redundant (parity check) bits to the message to minimize the efect of the noise. Codes that form a subspace of the vector space Z2 are called linear codes and are of particular importance. A key concept in the study of linear error correcting codes is the parity-check matrix.

A parity-check matrix is a matrix that, when multiplied by a binary string of appropriate length viewed as a vector, produces as the result of the multiplication the zero vector if and only if the string represents a code word (equivalently, the rows of a parity-check matrix of a linear code constitute a basis for the space orthogonal to the code space). It can also be used in decoding a message as well as in deciding whether a particular vector is a codeword. If is a parity check matrix, a code word belongs to a linear code block if and only if = 0 (for further details, the reader might consult the standard textbook [ 14 ]).

We say that a code is a low-density parity-check (LDPC) code if its parity-check matrix contains only a small number of 1’s. LDPC codes have an excellent performance with iterative decoding, which is very close to the Shannon limit over Additive White Gaussian Noise (AWGN) channels. These codes are constructed using bipartite graphs called Tanner graphs [ 18 ]. The Tanner graph of an LDPC code is composed of two sets of vertices (nodes); namely, variable vertices and check vertices.

Each variable and check vertex correspond to the number of a codeword and a parity symbol, respectively. If a variable vertex is constrained by a check vertex, then there is an edge connecting the two vertices. In addition, Tanner graphs are used to construct longer codes from smaller ones.

Example 8. We consider the parity check matrix used in the study of the girth of a Tanner graph of an LDPC code from [ 6 ]. By studying the Tanner graph of , we discovered that the graph of is the (3, 6)-cage, which is the Heawood graph.

⎛0 ⎜1 ⎜⎜0 = ⎜⎜1 ⎜⎜0 ⎜⎝1 0

Importantly, the girth of a Tanner graph giving rise to an LDPC code is an important factor that determines how good an LDPC code is, especially for regular LDPC codes, Quasicyclic LDPC codes, etc. For the regular LDPC codes, the girth of its Tanner graph is a lower bound of its minimum distance. In other words, it is a threshold to overcome the noise. Therefore, the bigger the girth, the better the LDPC codes. Recently, researchers have studied a class of LDPC codes with large girths, which they called Tanner (J, L)-regular QC-LDPC codes [ 20 ].

Their results showed that most Tanner (3, 5)-, (5, 7)-, (5, 11)- and (5, 13)-regular QC-LDPC codes have girths 6, 8 and 10 [ 20 ].

References

[1] Araujo-Pardo G. , Balbuena C. , and Héger T. : Finding small regular graphs of girths 6, 8 and 12 as subgraphs of cages . Discrete Math . 310 ( 2010 ) 1301 - 1306 .

[2] Balbuena C. , González-Moreno D. , and MontellanoBallesteros J. J.: A note on the upper bound and girth pair of ( , ) -cages . Discrete Appl . Math. 161 ( 6 ) ( 2013 ) 853 - 857 .

[3] Biggs N. L. : Constructions for cubic graphs of large girth . Electron. J. Combin . 5 ( 1998 ).

[4] Brown W. G. : On Hamiltonian regular graphs of girth 6 . J. London Math. Soc . 42 ( 1967 ) 514 - 520 .

[5] Conder M. , Exoo G. , and Jajcay R.: On the limitations of the use of solvable groups in Cayley graph cage constructions . Eur. J. Comb . 31 ( 7 ) ( 2010 ) 1819 - 28 .

[6] Dehghani H. , Ahmadi M. , Alikhani S. , and Hasni R.: Calculation of Girth of Tanner Graph in LDPC Codes . Trends in Applied Sciences Researchn 7 ( 2012 ) 929 - 934 .

[7] Erdős P. and Sachs H. : Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl . Wiss. Z. Uni . Halle (Math. Nat.) 12 ( 1963 ) 251 - 257 .

[8] Exoo G. and Jajcay R. : Dynamic cage survey . Electron. J. Comb., Dynamic Survey 16 ( 2013 ).

[9] Exoo G. and Jajcay R.: On the girth of voltage graph lifts . Eur. J. Comb . 32 ( 4 ) ( 2011 ) 554 - 562 .

[10] Feit W. and Higman G.: The nonexistence of certain generalized polygons . J. Algebra 1 ( 1964 ) 114 - 131 .

[11] Feng Y.Q. , Kutnar K. , Malnič A. , and Marušič D.: On 2 -fold covers of graphs . J. Comb. Theory, Ser. B 98 ( 2 ) ( 2008 ) 324 - 341 .

[12] Gács A. and Héger T. : On geometric constructions of (k,g)-graphs . Contrib. Discrete Math. 3 ( 2008 ) 63 - 80 .

[13] Gross J. L. and Tucker T. W. : Topological Graph Theory . Dover Mineola, New York ( 2001 ).

[14] Hill R.: A first course in coding theory . Oxford Applied Mathematics and Computing Science Series , Oxford, Clarendon Press. XII ( 1986 ).

[15] Hofman A. J. and Singleton R. R .: On Moore graphs with diameters 2 and 3 . IBM J. Res. Develop . 4 ( 1960 ) 497 - 504 .

[16] Imrich W. and Pisanski T. : Multiple Kronecker covering graphs . Eur. J. Comb . 29 ( 5 ) ( 2008 ) 1116 - 1122 .

[17] König D. : Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre . Math. Ann. 77 ( 1916 ) 453 - 465 .

[18] Tanner R. M.: A recursive approach to low complexity codes . IEEE Trans. Inform. Theory 27 ( 1981 ) 533 - 547 .

[19] Waller D. A. : Double covers of graphs . Bull. Aust. Math. Soc . 14 ( 2 )( 1976 ) 233 - 248 .

[20] Xu H. , Zhu H. , Miao X. , Xu M. , Luo Z. , and Li H.: A Short Note on the Girth of Tanner (5 ,13)- Regular QCLDPC Codes. 2021 17th International Conference on Computational Intelligence and Security (CIS) ( 2021 ) 449 - 453 . doi: 10 .1109/CIS54983. 2021 . 00099 .