Spectra of orders for k-regular graphs of girth g

Discussiones Mathematicae Graph Theory 41 (2021)1115–1125 https://doi.org/10.7151/dmgt.2233 SPECTRA OF ORDERS FOR k-REGULAR GRAPHS OF GIRTH g Robert Jajcay Department of Algebra and Geometry, Comenius University, Bratislava Mlynsk´a dolina, 842 48 Bratislava, Slovakia e-mail: [email protected] and Tom Raiman Department of Applied Mathematics Vˇ SB – Technical University of Ostrava 17. listopadu 15/2172, 708 33 Ostrava-Poruba, Czech Republic e-mail: [email protected] Abstract A (k, g)-graph is a k-regular graph of girth g. Given k≥2 and g≥3, infinitely many (k, g)-graphs of infinitely many orders are known to exist. Our goal, for given kand g, is the classification of all orders nfor which a (k, g)-graph of order nexists; we choose to call the set of all such orders the spectrum of orders of (k, g)-graphs. The smallest of these orders (the first element in the spectrum) is the order of a (k, g)-cage; the (k, g)-graph of the smallest possible order. The exact value of this order is unknown for the majority of parameters (k, g). We determine the spectra of orders for (2, g), g≥3, (k, 3), k≥2, and (3,5)-graphs, as well as the spectra of orders of some families of (k, 4)-graphs. In addition, we present methods for obtaining (k, g)-graphs that are larger then the smallest known (k, g)-graphs, but are smaller than (k, g)-graphs obtained by Sauer. Our constructions start from (k, g)-graphs that satisfy specific conditions derived in this paper and result in graphs of orders larger than the original graphs by one or two vertices. We present theorems describing ways to obtain ‘starter graphs’ whose orders fall in the gap between the well-known Moore bound and the constructive bound derived by Sauer and are the first members of an infinite sequence of graphs whose orders cover all admissible orders larger than those of the ‘starter graphs’. Keywords: cage, k-regular graph, girth, Sauer bound. 2010 Mathematics Subject Classification: 05C35, 05C07, 05C38, 05C75. 1116 R. Jajcay and T. Raiman 1. Introduction A (k, g)-graph is a k-regular graph of girth g. A (k, g)-cage is a smallest (k, g)- graph; its order is denoted by n(k, g). The question of the existence of (k, g)-graphs for any pair of kand ghas been resolved in the 1960’s [4, 10], however, the orders n(k, g) of (k, g)-cages have been only determined for a very small set of parameters [5]. The Moore bound gives a natural lower bound for the order of (k, g)-graphs (and therefore also for the order n(k, g) of the (k, g)-cages): (1) n(k, g)≥M(k, g) = (1 + k+k(k−1) + ···+k(k−1)(g−3)/2,if gis odd, 2(1 + (k−1) + ···+ (k−1)(g−2)/2),if gis even. It is known that the orders of the majority of cages exceed the value M(k, g) [5]. Graphs for which n(k, g) = M(k, g) are called Moore graphs and exist for only the following pairs of kand g:k= 2 and g≥3 (cycles), g= 3 and k≥2 (complete graphs Kk+1), g= 4 and k≥2 (complete bipartite graphs Kk,k), g= 5 and k= 2,3,7 (cycle, Petersen graph, Hoffman-Singleton graph), and g= 6,8,12 (a generalized n-gon of order k−1) [1, 3, 5]. The existence of a (57,5)-Moore graph is a long-standing open question. In the 1960’s Erd˝os and Sachs introduced an upper bound for the order of cages [4]. Their bound was later improved by Sauer. We denote the Sauer bound by S(k, g), [5, 11]: (2) n(3, g)≤S(3, g) = (4 3+29 12 2g−2,if gis odd, 2 3+29 12 2g−2,if gis even. For k≥4, (3) n(k, g)≤S(k, g) = (2(k−1)g−2,if gis odd, 4(k−1)g−3,if gis even. We will call (k, g)-graphs of order at least S(k, g) Sauer graphs. The significance of Sauer’s bounds lies in the fact that from the bound onwards there exists a (k, g)-graph of any admissible order greater than or equal to the corresponding Sauer bound. Thus, Sauer’s bounds are effectively orders of (k, g)-graphs having property that a (k, g)-graph exists for every admissible larger order. In view of the above results, we propose to extend the study of the orders of the (k, g)-graphs beyond searching for the smallest orders n(k, g) of cages, and classifying instead the entire spectrum of orders of (k, g)-graphs (with n(k, g) being the smallest among them). In this paper, we address this question by searching for recursive methods of constructing (k, g)-graphs via adding vertices Spectra of Orders for k-Regular Graphs of Girth g1117 and focusing on improvements to the Sauer bounds. Specifically, we look for (k, g)-graphs of orders smaller than the corresponding Sauer bound which are nevertheless ‘starter graphs’ and constitute the beginning of an infinite series of (k, g)-graphs whose orders cover all admissible orders greater than or equal to the order of our ‘starter graph’. We also seek general conditions that guarantee the existence of larger (k, g)-graphs constructed from smaller (k, g)-graphs. As both k-regularity and girth are, in a way, global properties, adding vertices to a (k, g)-graphs while preserving both its k-regularity and girth is surprisingly complicated. The results of Erd˝os, Sachs and Sauer [4, 10, 11], can be viewed as the first results concerned with determining the spectrum of orders for the (k, g)-graphs, with further partial results included in [2, 6] and [7]. However, not much is known about this question in general. While we will show later in this paper that (3,5)-graphs exist for every even order greater than or equal to the order 10 of the (3,5)-cage (the Petersen graph), a well-known gap in the spectrum of orders exists in the case of the (3,8)-graphs where the (3,8)-cage (the Tutte-Coxeter graph) is of order 30, while exhaustive search can show that no (3,8)-graphs exist of order 32 (and no (3,8)-graph of order 31 exists since the degree is odd) [9]. The following two theorems assert the existence of similar gaps in the spectra of orders of (k, g)-graphs for infinitely many parameter pairs (k, g). Theorem 1 [7].Let k≥2and g≥3. A (k, g)-graph of order M(k, g) + 1 exists if and only if k≥4is even and g= 3. Theorem 2 [7].Let k, g ≥6be both even. Then there exist no (k, g)-graphs of orders M(k, g) + e,1≤e≤k−2. We believe that better understanding of the order spectra of (k, g)-graphs would not only help us to improve the Sauer bound, which is currently roughly a square of the Moore bound, but it could possibly contribute to the resolution of the longstanding question of the existence of the (57,5)-Moore graph. The existence problem for the (57,5)-Moore graph could be resolved in negative if one could find an argument that would imply that the existence of the Moore (57,5)-graph would also force the existence of a series of graphs Γ0,Γ1,...,Γs recursively constructed from the hypothetical Moore graph (denoted by Γ0) and having increasing orders, and then prove the non-existence of one of the graphs in the series; thereby making the assumption about the existence of the (57,5)- Moore graph false as well. 2. The Spectra of Orders for the Parameters (2, g),(k, 3) and (k, 4) We begin the section by stating and proving a very simple lemma. The reason we include the proof of this lemma is the fact that its proof contains a fundamental 1118 R. Jajcay and T. Raiman idea that will reappear in a more complicated way in our later results. Although it is well-know that 2-regular Moore graphs exist for every g(i.e., cycles of length g), we are interested in the existence of larger 2-regular graphs of girth exactly g. The next lemma characterizes the entire spectra of orders for (2, g)-graphs for all g≥3; the type of results we seek in our paper. We show that, in this case, the spectra of orders are not continuous. Lemma 3. Let g≥3. A (2, g)-graph of order nexists if and only if nis one of the numbers M(2, g),2M(2, g),2M(2, g) + 1,2M(2, g) + 2,.... Proof. Let Gbe the Moore 2-regular graph of order g. Since any 2-regular graph consists necessarily of a union of disjoint cycles, and we want graphs whose girth is exactly g, any (2, g)-graph must consist of a g-cycle and possibly other cycles of length at least g. Thus, any (2, g)-graph either consists of a single g-cycle of order M(2, g) or has to contain at least gadditional vertices that form a second cycle of length at least g. It follows that any (2, g)-graphs of order greater than g=M(2, g) must be of order at least 2g= 2M(2, g), and it is easy to see that choosing the second cycle of length g+i=M(2, g)+i,i≥0, yields a (2, g)-graph of order 2M(2, g) + i, for every i≥0, as claimed in our lemma. It follows from the proof of Lemma 3 that the spectrum of orders of the (2, g)-graphs contains a gap, but becomes continuous after reaching the value 2M(2, g). Specifically, in case of (2, g)-graphs we have a situation where a (k, g)- graph exists for a specific order (value of the Moore bound) and then the orders form a gap after which (2, g)-graphs exist for all larger orders. As we will show later by proving that (3,5)-graphs exist for all even orders starting from the order of the Moore (3,5)-graph, the Petersen graph, no such gap is necessary. To the best of our knowledge, no pair of parameters (k, g) which admit for the existence of two separated gaps of sizes greater than 1 is known. Next, let us consider graphs with girths 3 and 4. It is known that their respective Moore graphs are the graphs Kk+1 and Kk,k. Before we proceed with the proof for (k, g)-graphs where g= 3, we need to define a concept well-known in algebraic graph theory, namely that of a circulant. Let 0 < a1< a2<···< ar< n be an increasing sequence of integers. A circulant Cn(a1, a2,...,ar) is a graph G(V, E) on nvertices v0, v1,...,vn−1with the edge set E={vivi+aj: 0 ≤i≤n−1∧1≤j≤r}, where the addition in the indices is performed modulo n. Lemma 4. 1. If k≥4is even, there exists a (k, 3)-graph of any order greater than or equal to the Moore bound M(k, 3) = k+ 1. 2. If k≥3is odd, a (k, 3)-graph exists of every even order greater than or equal to the Moore bound M(k, 3) = k+ 1. Spectra of Orders for k-Regular Graphs of Girth g1119 Proof. Let nbe the order of the desired graph, and let us denote its vertices by v0, v1,...,vn−1. We first prove the theorem for k= 3. Since the degree of the graph is odd, its order nmust be even and greater than or equal to M(k, 3) = 4. Any such graph can be obtained by adding the edges {v0, vn 2}, {vi, vn−i}, 0 < i < n 2, into the n-cycle formed by the edges vivi+1, for 0 ≤i≤n−1. Clearly, each vertex of such graph is of degree 3 and each of these graphs contains at least one 3-cycle (e.g., vn−1, v0, v1). See Figure 1(a). Next, to cover the case of even regularity 2k, k ≥2, and n≥M(2k, 3) ≥ 2k+ 1, we will use the circulants Cn(1,2,...,k). Since k < n 2, all vertices of this graph are of a degree 2k, and there is the 3-cycle vn−1, v0, v1. See Figure 1(b). Finally, consider the regularity 2k+ 1, k ≥2. Since kis odd, the order n≥M(2k+ 1,3) ≥2k+ 2 is even. We use the circulants Cn(1,2,...,k) again and add the edges vivi+n/2, for 0 ≤i≤n 2−1. In this case all vertices are of degree 2k+ 1 and there is a 3-cycle vn−1, v0, v1. See Figure 1(c). (a) (3,3)-graph of order 8 (b) (4,3)-graph of order 8 (c) (5,3)-graph of order 8 Figure 1. Graphs of girth 3. We see that in case of girth 3 and even kthere exist connected (k, 3)-graphs for every order greater than or equal to the Moore bound M(k, 3). For odd k, a connected (k, 3)-graph exists for every even order greater than or equal to the Moore bound M(k, 3). Next, we show a similar result for girth 4. Lemma 5. For each integer k≥3and each even integer n≥M(k, 4), there exists a (k, 4)-graph of order n. Proof. Let n= 2m≥M(k, 4) and let us divide the vertices of the potential graph into two disjoint sets of size m. Let us denote the vertices in the first set by v0,1, v1,1,...,v(m−1),1, and the vertices in the second set by v0,2, v1,2,...,v(m−1),2. It follows from the Moore bound that k≤m. For each 0 ≤i≤m−1, we connect the vertex vi,1to the vertices v(i+j),2, for 0 ≤j≤k−1, with the addition performed modulo m. Clearly, all the vertices in the first set are of degree k. Similarly, vertices in the second set are also of degree k; with each vertex vi,2, 1120 R. Jajcay and T. Raiman 0≤i≤m−1, connected to the vertices v(i−j),1, for 0 ≤j≤k−1 and the subtraction performed modulo m. Since the graph is bipartite, its girth is at least 4, and it contains the 4-cycle v0,1, v1,2, v1,1, v2,2, v0,1. See Figure 2. Figure 2. (4,4)-graph of order 14. If kis odd, this is, of course, the best possible result, since the order of a k-regular graph with odd kmust necessarily be even. Interestingly, in the case of even k, we have been unable to find a general construction for (k, 4)-graphs of odd orders close to the Moore bound. To begin with, Theorem 1 asserts that there exist no (k, 4)-graphs of order M(k, 4) + 1 (regardless of the parity of k). On the other hand, for even k, the Sauer bound yields that starting from S(k, 4) = 4(k−1), there exist (k, 4)-graphs of all orders including the odd ones. In the particular case of (4,4)-graphs, we can construct (4,4)-graphs of orders 11 and 13 recursively from (4,4)-graphs of order 10 and 12 using Theorem 8 proved later in this paper. Thus, the order spectrum of the (4,4)-graphs consists of all integers greater than or equal to 8 except for the number 9. In the case of the (6,4)-graphs, Meringer proved by computer search that there exist (6,4)-graphs of orders 15,17 and 19 [9], giving us the order spectrum for the (6,4)-graphs consisting of all integers greater than or equal to 12 but excluding the number 13. Even though the above two examples might be viewed as evidence toward a claim that the order spectrum of all (k, 4)-graphs with even kconsists of all integers greater than or equal to 2kwith the exception of 2k+ 1, we have been unable to prove such general result. As pointed out by one of our referees, using one of the standard construction algorithms yields no (8,4)-graph on 19 vertices for more than two hours. Thus, (8,4)-graphs may not exist for more than just one order larger than the Moore bound, and no general result of the kind suggested above may actually be proved. 3. Conditions for Adding Vertices in (k, g)-Graphs In this section, we present recursive constructions based on adding vertices to Spectra of Orders for k-Regular Graphs of Girth g1121 graphs while preserving their degree and girth. Before we turn our attention to (k, g)-graphs with k≥3 and g≥5, we need to define the distance between edges in a graph. Let eand fbe two edges of a graph G. The edge distance between eand fis the length of the shortest path between any vertex of eand any vertex of f. First we state a theorem for graphs of regularity 3, where the situation differs from (k, g)-graphs with higher regularities. Theorem 6. Let Γbe a (3, g)-graph of order n. If Γhas at least two edges of distance at least g−3, then there exists a (3, g)-graph Γ′of order n+ 2. Proof. Let Γ be a (3, g)-graph of order n. If Γ contains two edges of distance at least g−3, it also contain two edges, say eand f, of distance exactly g−3. We subdivide each of these edges by introducing an additional vertex in the middle; vertex xin the edge eand vertex yin the edge f. Because of our assumptions about the distance between eand f, the distance between xand yis exactly g−1. Adding the edge xy increases the degrees of xand yto 3, which makes the resulting graph Γ′that has two more vertices and one additional edge into a 3-regular graph. Since the distance between xand ywas g−1, by adding the new edge we have created a cycle of length g. At the same time, we have not altered the length of any cycle which does not include either of the vertices xor y, while the lengths of the cycles that now contain xor yhas either remained the same or increased. Thus, the resulting graph has two more vertices, contains a cycle of length g, and all of its other cycles are of length at least g. Hence, Γ′is a 3-regular graph of girth gcontaining two more vertices than Γ. Thus, any (3, g)-graph Γ of order nsatisfying the conditions of the above theorem gives rise to at least one (3, g)-graph of order n+ 2 and girth exactly g. This is of particular importance when one tries to construct a recursive series of (3, g)-graphs. Example 7. We demonstrate this approach starting with the Petersen graph (the (3,5)-cage of order 10); see Figure 3(a). Since the Petersen graph is edgetransitive, we can pick any of its edges for the initial edge e(denoted red in Figure 3(a)). There is at least one edge at distance at least 2 (black edges), while the blue and green edges are at distance 0 and 1 from the red edge. By subdividing the red and one of the two black edges and introducing the extra edge, we obtain a (3,5)-graph of order 12. Applying Theorem 6 again, we can construct a series of (3,5)-graphs of orders 12,14,16,18. There is no need to go beyond the value 18, since S(3,5) = 4/3 + 12/29.23= 20 and (3,5)-graphs of higher orders exist due to the results of Sauer. All of the above yields the spectrum of orders for the (3,5)-graphs that consists of all even integers greater than or equal to 10. 1122 R. Jajcay and T. Raiman (a) (3,5)-graph (b) (3,5)-graph (c) (3,5)-graph (d) (3,5)-graph of order 12 of order 14 of order 16 of order 18 Figure 3. Adding vertices to Petersen graph, where red edge is the initial edge, blue edges are edges at distance 0, green edges are at distance 1, black edges are at distance 2 and the grey edge is the added edge. Our next theorem provides us with a recursive construction for regular graphs of even degrees. This will enable us to add just a single vertex. Theorem 8. Let Γbe a (2k, g)-graph of order n. If Γhas at least kedges whose pairwise distances are at least g−2, and if at least one pair of these edges is at the distance exactly g−2, then there exists a (2k, g)-graph Γ′of order n+ 1. Proof. To prove the theorem, we subdivide the kspecial edges in Γ by introducing knew vertices of degree 2, and then identify the new vertices into a single vertex denoted v. Then vis clearly of degree 2k, and the new graph Γ′is a 2k-regular graph. It remains to prove that the length of the shortest cycle in Γ′is at least g. Before adding v, we have chosen edges with mutual distances at least g−2. Thus, the new subdivision vertices are of mutual distance at least g, and identifying them into a single vertex will form cycles involving vof length at least g. None of the cycles not involving vhas been shortened in this process, and thus the girth of Γ′is at least g. The two edges of exact distance g−2 give rise to at least one cycle of length exactly g. Example 9. This time, we start of the Robertson graph, the (4,5)-cage of order 19. It is not hard to find two edges of distance 3 in this graph. In Figure 4 we colored the two edges red and black again (with the rest of the edges colored blue, purple, and green, denoting the distances 0, 1, and 2 from the red edge, respectively). Identifying the two vertices subdividing the red and the black edge into a single grey vertex yields a (4,5)-graph of order 20. In our last condition for adding vertices in (k, g)-graphs, we will consider graphs of odd degree 2k+ 1. In this case, mimicking the process from Theorem 8, we will form two vertices of degree 2k, which we will subsequently join by an edge. Assuming the right properties, we will end up with a (2k+1)-regular graph of the same girth as the starting graph. We leave the proof of this theorem to the reader. Spectra of Orders for k-Regular Graphs of Girth g1123 Figure 4. (4,5)-graph of order 20. Theorem 10. Let Γbe a (2k+ 1, g)-graph of order n. If Γcontains two disjoint sets U, V , each consisting of kedges of pairwise distances at least g−2and at least one pair of edges at distance exactly g−2, and if all the edges from Uare at distance at least g−3from all the edges in V, then there exists a (2k+1, g)-graph Γ′of order n+ 2. 4. Final Remarks Even though we have proved the conditions for extending (k, g)-graphs while preserving their degree and girth introduced in the previous section to be sufficient, the non-existence of graphs satisfying these conditions does not necessarily mean the non-existence of larger graphs. For example, our methods fail to extend the Heawood graph (the (3,6)-cage of order 14) as well as the Tutte-Coxeter graph (the (3,8)-cage of order 30) (these two graphs contain no two edges of distance 3 or 5, respectively). Nevertheless, a (3,6)-graph of order 16 exists, while a (3,8)-graph of order 32 does not [9]. This reflects the fact that our methods do not constitute the only way to add vertices to (k, g)-graphs while keeping their properties. In [7], the authors present another way for extending the Petersen graph. Their method relies on finding an even-length cycle of length being a multiple of the degree of the graph, deleting every other edge in this cycle (thereby making all the vertices of the cycle into degree 2 vertices), and attaching additional vertices to the deficient vertices. Yet another method was introduced by Meringer in [8, 9], which starts from an empty