A (, )-graph Γ, ≥ 2, ≥ 3, is -regular of girth . We refer to the complete set of possible orders of connected (, )-graphs for each pair of parameters (, ) as the spectrum of orders of (, )-graphs; or the (, )-spectrum. The smallest member of the (, )-spectrum is the order (, ) of a smallest (, )-graph; called a (, )-cage. Determining the complete spectrum of orders of connected (, )-graphs for a specific pair (, ) is extremely dificult as it requires (among other things) determining the cage order (, ), which is a notoriously hard problem. This paper provides an algorithmic approach for producing (, )-graphs of larger orders from smaller (, )-graphs in a manner allowing for repeated applications. We use this approach to determine/estimate the smallest member (, ) of a (, )-spectrum having the property that starting from (, ) all (even; in case of odd ) ≥ (, ) belong to the (, )-spectrum; i.e., for all (even) ≥ (, ), there exists a (, )-graph of order .
some connected (, )-graph. Furthermore, in view of the results in [1], each (, )-spectrum contains a smallThe girth of a (finite) graph Γ is the length of a smallest est positive integer (, ) such that all (even, in case of cycle in Γ; we will always assume that our graphs contain odd ) integers ≥ (, ) are contained in the spectrum. at least some cycles and are connected; they are not trees It is important to note that the number (, ) is not necor forests. A (, )-graph Γ, ≥ 2, ≥ 3, is a connected essarily equal to the order (, ) of a cage. Specifically, -regular of girth . A (, )-graph Γ of minimum order it is well-known that while (3, 8) = 30, there exists no (, ) is called a (, )-cage, and the problem of finding (3, 8)-graph of order 32, and thus (3, 8) ≥ 34 [3]. the (, )-cages and establishing their orders is called the The problem of determining the entire (, )-spectra Cage Problem. It is well known that for any given pair of for specific parameter pairs (, ) was probably for the parameters (, ), there are infinitely many connected ifrst time earnestly approached in [ 3]. Since the prob(, )-graphs [1], which results in an infinite set of orders lem of determining the cage orders (, ) is already of (, )-graphs for each pair (, ). More precisely, the famously dificult (and solved only for limited sets of results obtained in [1] not only establish the existence parameter pairs), it is clear that one cannot reasonably of a (, )-graph of order ≤ 4 ∑︀=−12( − 1), for every expect to establish the (, )-spectra for all pairs (, ). ≥ 2, ≥ 3, but assert the fact that (, )-graphs exist For example, the results obtained in [3] include the defor all larger orders as well (for all even larger orders in termination of the (, )-spectra for the pairs (2, ) for case of odd ). Unfortunately, the arguments used in [1] ≥ 3, and (, 3) and (, 4) for ≥ 3. are probabilistic and non-constructive. In determining the complete spectra of orders of (, )
The complete set of orders of connected (, )-graphs graphs, one usually starts from a Moore graph or a cage for a pair of parameters (, ) will be referred to as the and proceeds to construct larger (, )-graphs using varspectrum of orders of (, )-graphs; or the (, )-spectrum. ious construction methods. These methods include exciClearly, the smallest element in the (, )-spectrum for sion/addition methods (removal/addition of vertices or a specific pair , is the order (, ) of the (, )-cage, edges), voltage graph construction, and others; combined and any member of the (, )-spectrum is the order of with extensive computer searches. The methods used in [3] include a recursive construction approach based on (2I3TrAdTC)o,n22fe.9re–n2c6e.9o.n20I2n3fo,rHmoatetlioHnuttenchíknoI,loTgaitersa–nAskpéplMicaattliioanrse,aSnldovTahkeioary adding vertices generalizing one of the constructions $ leonard.eze@fmph.uniba.sk (L. C. Eze); used in [4] for constructing two (3, 5)-graphs of order robert.jajcay@fmph.uniba.sk (R. Jajcay); 12 from the Petersen graph (shown in Figure 1 and 2). dominika.mihalova@fmph.uniba.sk (D. Mihálová) Since the method described in [4] used for constructing © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License two (3, 5)-graphs of order 12 from the Petersen graph CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) is also the basis of most of the methods presented in ing cycles, and in Section 4 we summarize the usage of here, we include brief descriptions of the constructions. the results and constructions of Sections 2 and 3 in an It is interesting to point out that the two constructed algorithmic way. (3, 5)-graphs of order 12 are the only (3, 5)-graphs of this order.
The first (3, 5)-graph of order 12 (seen in Figure 1) 2. Additive Properties of was constructed from the Petersen graph by selecting a 6- (, )-Spectra cycle (depicted by vertices 1, 2, 3, 4, 5, 6), deleting the three red edges, and adding two vertices of degree In this section, we present recursive techniques for build3 to the 6 vertices of the original 6-cycle. By attaching ing series of (, )-graphs from a given starting (, )each of the two vertices to one of the end-points of each graph that will provide us with a better understanding of the remaining 3 edges of the original 6-cycle, a (3, 5)- of the properties of the (, )-spectra. graph of order 12, which contains no cycle of length less We begin by introducing a simple construction that than 5 is obtained (see Figure 1). will allow us to combine existing (, )-graphs into a larger (, )-graph.
Lemma 1. Assume that ≥ 3, ≥ 3, and let Γ1, Γ2 be two (, )-graphs of orders and , respectively, with the additional property that at least one of the two graphs contains an edge not contained in a -cycle or contains two distinct -cycles that difer in at least one edge. Then there exists a (, )-graph Γ of order + .
Figure 1: (3, 5)-Graph of order 12 (right) obtained from the Γ1 contains an edge not contained in a -cycle or or conPetersen graph (left) tains two distinct -cycles that difer in at least one edge.
The second (3, 5)-graph of order 12 (seen in Figure In the first case, let be an edge of Γ1 that is not con2) was again constructed from the Petersen graph by tained in a -cycle, and in the second case, let be any selecting a 6-cycle (depicted in red), choosing any two edge of Γ1 contained in at most one of the two distinct opposing edges of the 6-cycle, subdividing them via in- -cycles. Further, let ′′ be any edge of Γ2. Construct Γ troducing a new vertex to each of the selected edges and to be the graph with vertex set (Γ1) ∪ (Γ2) and edge thereafter joining the two new vertices via an edge. set (Γ1) ∪ (Γ2) minus the selected edges , ′′, which are replaced by the edges ′ and ′. Clearly, Γ is a -regular graph, and to prove the theorem, we just need to prove that the girth of Γ is . Because of our choice of the edge , it is easy to see that Γ contains at least one -cycle (originally contained in Γ1).
Thus, to finish the proof, we need to show that Γ does not contain cycles shorter than . Suppose, by means of contradiction, that Γ does contain a cycle of length smaller than . Since both graphs Γ1 and Γ2 are of girth Figure 2: (3, 5)-Graph of order 12 (right) obtained from the , any such cycle must contain both of the added edges Petersen graph (left) ′, ′, and must be of the form , ′, 12, 22, . . . , 2 = ′, , 11, 21, . . . , 1 = , with any two consecutive ver
Since determining the entire spectrum of orders of tices adjacent, and the vertices with superscript con(, )-graphs for a specific pair (, ) would also mean tained in Γ. To obtain the desired contradiction, note determining the cage order (, ), instead of attempt- that the vertices , , 11, 21, . . . , 1 = necessarily ing to determine the entire spectra, we focus on finding form a cycle in Γ1; which is of girth . Hence, + 1 ≥ , (upper bounds on) the numbers (, ) for specific pa- and by a symmetric argument, + 1 ≥ as well. It folrameter pairs (, ). Our approach is algorithmic in the lows that the length of is at least 2 + 2 which clearly sense that we try to design methods that produce larger contradicts the assumption that is of length smaller (, )-graphs from smaller (, )-graphs in a manner al- than . lowing for repeated application.
The paper is organized as follows: Section 2 contains Corollary 2. Let ≥ 3 and ≥ 3. The (, )-spectrum some basic additive properties of (, )-spectra, Section contains all positive integral multiples of (, ). 3 introduces constructions based on adding vertices usProof. Since ≥ 3 and ≥ 3, it is easy to see that Clearly, Γ* is 3-regular, and contains a 6-cycle, e.g., (, ) > + 1, and therefore any (, )-graph must 1, 6, 5, 2, 3, 4, 1. It remains to prove that Γ* either contain an edge that does not belong to any -cycle does not contain cycles shorter than 5. To see that, note or contains two distinct -cycles. Let Γ1 be a (, )-cage ifrst that since the girth of Γ is 5, and the vertices 2, 3 of order (, ). Since the order of Γ1 is (, ), Γ1 are adjacent in Γ, after removing their shared edge, they either contains an edge that does not belong to any - must be of distance at least 4 (as otherwise we would cycle or it contains two distinct cycles. Thus, based on have a 3- or a 4-cycle in Γ). As no path between these Lemma 1, it can be used to construct a sequence Γ, ∈ N, two vertices of length shorter than 3 has been added into defined recursively via constructing Γ+1 by combining Γ* , it is easy to see that the distance between 2 and Γ1 and Γ, for all ≥ 2. Due to Lemma 1, all the graphs 3 in Γ* is still at least 3. The same is true for the pairs Γ are (, )-graphs of orders · (, ), ∈ N. 4, 5 and 6, 1, and even more importantly, the length of any path between any two neighbors of 1 not using Corollary 3. Let ≥ 3 and ≥ 3. 1 is at least 3, as their distance in Γ was originally 2.
If is even and there exists an such that all the con- The same holds for any two neighbors of 2. By means secutive integers , + 1, + 2, . . . , + (, ) − 1 of contradiction, assume now that Γ* contains a cycle of belong to the (, )-spectrum, then all ≥ belong to length shorter than 5. Any such cycle must contain at this spectrum, and ≥ (, ). least one of the new vertices 1, 2. Should such cycle
If is odd and there exists an even such that all contain both vertices 1 and 2, since they are of distance the consecutive even integers , + 2, + 4, . . . , + 3, it would have to be at least a 6-cycle. If it contained just (, ) − 2 belong to the (, )-spectrum, then all even one of them, it would also have to contain its neighbors, ≥ belong to this spectrum, and ≥ (, ). but any two neighbors of any of the vertices 1, 2 are of distance at least 3 and hence the length of such cycle would have to be at least 5. Hence, Γ* contains no cycles shorter than 5 and the proof is complete.
Proof. In case of even , all the graphs Γ constructed in the proof of Corollary 2 either contain an edge that does not belong to any -cycle or contain two distinct -cycles. Since , + 1, + 2, . . . , + (, ) − 1 belong to the (, )-spectrum, there exist (, )-graphs Δ , ≤ ≤ + (, ) − 1, of orders , + 1, + 2, . . . , + (, ) − 1, respectively. Using Lemma 1 to combine the graphs Δ with the graphs Γ yields the desired family of (, )-graphs whose orders cover all positive integers greater than or equal to .
If is odd, the order of any (, )-graph is even, while the rest of the proof follows essentially along the same line as the case of even .
Corollary 5. The spectrum of orders of (3, 5)-graphs is the set of all even integers greater than or equal to 10.
(see, for example, the outer 6-cycle in Figure 1). Add the vertices 1, 2 and the six new edges as described in Lemma 4. Choose one of the two new 6-cycles, and note that it only contains two of the three original edges of the 6-cycle in the Petersen, and so no further change of the selected 6-cycle will afect the fact that the third edge originally contained in the 6-cycle of the Petersen graph is (and will remain) contained in a 5-cycle. By always adding new vertices to 6-cycles added in the previous step, we will construct an infinite sequence of (3, 5)graphs (all containing at least one 5-cycle and at least one 6-cycle) of orders 10, 12, 14, 16, . . ..
(, )-graphs assuming the existence of an additional cycle of certain length greater than in the starting graph. We first illustrate our approach by (re)determining the order spectrum of the (3, 5)-graphs (already achieved in [3]).
not be used in case of (3, 6)-graphs as it may occasionally create a 5-cycle, there are cases where applying the conLemma 4. Let Γ be a (3, 5)-graph of order containing struction to a specific 6-cycle in a (3, 6)-graph of order a 6-cycle. Then there exists a (3, 5)-graph of order + 2 yields a (3, 6)-graph of order + 2. One such case that also contains a 6-cycle. appears when one attaches two vertices to a 6-cycle in the Heawood graph. See Figure 3.
Proof. Let be a 6-cycle in Γ consisting of the ver- Although the construction described in Lemma 4 can tices 1, 2, 3, 4, 5, 6, with any two consecutive be generalized into infinitely many new (similar) lemmas, vertices adjacent. To construct the (3, 5) graph Γ* we only introduce two such generalizations. The reason from Γ, remove the three edges 23, 45, and for not trying to present all such lemmas is the fact that 61, and add two new vertices 1, 2 together with in general we do not have such a convenient starting six new edges 21, 41, 61, 12, 32 and 52. point as is the Petersen graph in Corollary 5, and hence desired ( 32 − 3) cycle in a (3, )-cage is not guaranteed. For example, if the Tutte-Coxeter graph, the (3, 8)cage of order 30, contained cycles with the properties described in Lemma 6, it would imply the existence of a (3, 8)-graph of order 32. However, as already pointed out in the Introduction, it is well known that no such graph exists.
In particular, since the Tutte-Coxeter graph is the point-line incidence graph of a generalized quadrangle of order 2, it is bipartite, and therefore contains no 9-cycles, while the minimal length of the cycle required in the lemma is at least ( 32·8 − 3) = 9. On the other hand, the existence of a (3, 8)-graph of order 34 containing a 9cycle of the desired properties would yield a (3, 8)-graph of order 36 and might be the beginning of the continuous part of the (3, 8)-spectrum (i.e., it might be the case that (3, 8) = 34). At this point, we have not yet determined whether such graph on 34 vertices exists.
We conclude the section with one more analogue of Lemma 4. we cannot use the forthcoming lemmas to obtain results of similar strength to those of Corollary 5. Even though these lemmas do allow one to add two vertices to an existing (3, )- or (4, )-graph in a way resulting in a larger (3, )- or (4, )-graph, finding graphs satisfying the required properties is hard, and one does not have any guarantee that the process of adding two vertices can be recursively repeated. Therefore, these lemmas are best seen as starting points for computer assisted constructions.
Lemma 7. Let ≥ 8 be even, and let Γ be a (4, )-graph of order containing a cycle of length at least (2 − 2) which contains edges 12, 34, 56, and 78 such that the distances between the pair of vertices 1, 8, the pair of vertices 2, 3, the pair of vertices 4, 5 and the pair of vertices 6, 7 in Γ are at least 2 − 2 and the distances between any two of the vertices 1, 3, 5, 7 and the distances between any two of the vertices 2, 4, 6, 8 Lemma 6. Let ≥ 8 be even, and let Γ be a (3, )-graph in the graph Γ − 12 − 34 − 56 − 78 (Γ with of order containing a cycle of length at least ( 32 − 3) four edges removed) are at least − 2. In addition, let Γ which contains edges 12, 34, and 56 such that contain at least one -cycle that does not contain any of the distances between the pair of vertices 1, 6, the pair the edges 12, 34, 56, or 78. Then there exists a of vertices 2, 3 and the pair of vertices 4, 5 in Γ are (4, )-graph Γ* of order + 2. at least 2 − 2 and the distances between any two of the vertices 1, 3, 5 and the distances between any two of the Proof. We leave it to the reader to verify that the graph vertices 2, 4, 6 in the graph Γ − 12 − 34 − 56 Γ* constructed from Γ described in the lemma via the (Γ with three edges removed) are at least − 2. In addition, removal of the edges 12, 34, 56, 78, and let Γ contain at least one -cycle that does not contain adding vertices 1, 2 adjacent to 1, 3, 5, 7 and any of the edges 12, 34, or 56. Then there exists a 2, 4, 6, 8 respectively, is a (4, )-graph. (3, )-graph Γ* of order + 2.
Lemma 4. Let be a cycle in Γ of length at least ( 32 − 3), and let 12, 34 and 56 be edges of with the properties described in the lemma. The desired graph Γ* can then be constructed from Γ by removing the edges 12, 34 and 56, and adding new vertices 1 and 2 with 1 adjacent to the vertices 1, 3 and 5 and 2 adjacent to the vertices 2, 4 and 6 (in the same manner as in the proof of Lemma 4). We leave it to the reader to verify that since Γ is of girth , Γ* contains no cycles shorter than and contains at least one -cycle (the -cycle not containing the three removed edges).
Let us begin the section by combining the approaches introduced in Sections 2 and 3. Recall that for any pair of positive integers and , the gcd(, ) is a sum of integral multiples of and , and moreover, there exists an integer such that all integral multiples of gcd(, ) greater than or equal to · gcd(, ) are sums of positive integral multiples of and . Hence, in case of even and any ≥ 3, the existence of (, )graphs of relatively prime orders and yields, via using Lemma 1, the existence of (, ) as defined in the Introduction (and proved to exist in [1]). Similarly, Algorithm 1 Remove3EdgesAdd2Vertices(graph) in case of odd and any ≥ 3, the existence of (, )- for all combinations of 3 edges as graphs of orders 2 and 2, with and relatively do prime, yields by Lemma 1 the existence of (, ) again. verticesToReconnect = Flat(removedEdges)
Since gcd(, +1) = 1 and gcd(2, 2+2) = 2, Sec- graphWithoutEdges = RemoveEdges(graph, retion 3 provides one with the possibility of constructing movedEdges) consecutive pairs of even orders yielding the existence graphWithVertices = AddVerof (, ). The only drawback of using the lemmas con- tices(graphWithoutEdges, 2) tained in Section 3 is the requirement of using graphs con- possibleGraphs = ConnectVertaining the specific cycles of length greater than . Since tices(graphWithVertices, verticesToReconnect) no universal constructions of such graphs are known, one has to rely on computer searches. graphsWithCorrectGirth = Check
In this section, we present an algorithm for searching Girth(possibleGraphs, Girth(graph)) for graphs described in the previous sections. We imple- if graphsWithCorrectGirth not empty then mented our algorithm (Algorithm 1) in the system for newGraphs = GetUnisomorphicdiscrete computational algebra - GAP version 4.12.2 and Graphs(graphsWithCorrectGirth) used two packages: DIGRAPHS and GRAPE. end if
The input for our algorithm is the graph object from end for GRAPE package. In a for-cycle, we go through all com- return newGraphs binations of three edges, which we will later remove.
We store the edges in a removedEdges variable. The names of vertices of those edges are saved in variable advantage of these programs. Thus the above summary verticesToReconnect as we will need their names of results obtained using our programs should be seen as to connect them with the new two vertices. In the just examples of the use of our techniques. For example, next step we remove the edges in removedEdges with as stated in the previous section, in order to obtain a the function RemoveEdges() and obtain a new graph characterization of the order spectrum of (3, 8)-graphs, object (graphWithoutEdges). Then, we add the two we would need to find a smallest (3, 8)-graph containing new vertices with AddVertices(), which returns a a 9-cycle (which must be of order at least 34). As this graph object (graphWithVertices). To obtain all pos- does not seem to be out of reach, a more persistent use sible cubic graphs in this iteration through combina- of these programs might eventually lead to new results. tions of edges, we connect the two new vertices with vertices in verticesToReconnect with the function ConnectVertices(). The functions RemoveEdges() 6. Acknowledgments , AddVertices() and ConnectVertices() use com- All three authors acknowledge the support from VEGA mands from the DIGRAPHS package. We store all graphs 1/0437/23 and the second author is also supported by with the same girth as the original graph in variable APVV-19-0308. The authors also wish to thank the anonygraphsWithCorrectGirth. If the list of graphs with mous referee for his/her insightful comments and sugrequired girth is not empty, we check for isomorphic gestions. graphs and keep only non isomorphic ones. The function returns a list of non isomorphic graphs with the excess 2.
Using Algorithm 1, starting from the Petersen graph, References we found 2 graphs with two additional vertices, 8 graphs with four additional vertices, and 48 graphs with six [1] Erdős P. and Sachs H.: Reguläre Graphen gegebener additional vertices. Starting from the McGee graph, we Taillenweite mit minimaler Knotenzahl. Wiss. Z. Uni. found 1 graph with one additional vertex, 1 graph with Halle (Math. Nat.) 12 (1963) 251–257. four additional vertices, and 6 graphs with six additional [2] Exoo G. and Jajcay R.: Dynamic cage survey. Elecvertices. For the (3, 11)-cage, we found 2 graphs with tron. J. Comb., Dynamic Survey 16 (2013). two additional vertices. [3] Jajcay R. and Raiman T.: Spectra of Orders for -Regular Graphs of Girth . Discussiones Mathematicae Graph Theory, 41(4) (2021) 1115–1125. 5. Conclusion https://doi.org/10.7151/dmgt.2233 In conclusion, let us point out that the above computer [4] Jajcayová T. B., Filipovski S. and Jajcay R.: Counting implementation of our algorithms has been developed in cycles in graphs with small excess. Lecture Notes of parallel and somewhat independently of our theoretical Seminario Interdisciplinare di Matematica, 2016. results. That did not leave enough time for us to take full