Goal-minimally π‘˜-diametric graphs with not so small diameters Ε tefan GyΓΌrki Slovak University of Technology, Bratislava, Slovakia Abstract An undirected graph Ξ“ with diameter π‘˜ is said to be goal-minimally π‘˜-diametric if for every edge 𝑒𝑣 of Ξ“ the distance π‘‘Ξ“βˆ’π‘’π‘£ (π‘₯, 𝑦) > π‘˜ if and only if {π‘₯, 𝑦} = {𝑒, 𝑣}. It is rather difficult to construct such graphs. Before our research, they were known only for diameters up to 14, except of the case π‘˜ = 11. In this paper we construct such graphs of larger diameters using Cayley graphs with generators obtained by linear fractional transformations on the set of elements of a finite field GF(π‘ž) extended by an element ∞. Keywords Computer algebra, Distance, Diameter, Edge deletion, Goal-minimal, Cayley graphs 1. Introduction family of 6-GMD graphs. GyΓΌrki [14] constructed by lifts the first known 9-GMD and 13-GMD graphs, moreover, Minimal graphs with respect to diameter were studied he found an infinite family of 5-GMD graphs. Thus, be- by many authors, for example see [1], [3], [7], [9], [11], fore our research such graphs have been known only for [12], [17] and [18]. A special subclass of this class of values π‘˜ ≀ 14, except of the case π‘˜ = 11. graphs are so-called goal-minimal graphs with respect In this paper we construct π‘˜-GMD graphs as Cayley to diameter which were introduced by KyΕ‘ in [16] and graphs with generating set obtained from linear frac- studied by Gliviak and PlesnΓ­k in [10], [19] and by GyΓΌrki tional transformations on GF(π‘ž) βˆͺ {∞}, having larger di- in [13] and [14]. ameters. A graph Ξ“ with diameter π‘˜ is called a minimal graph The most important properties of π‘˜-GMD graphs are of diameter π‘˜ if diam(Ξ“ βˆ’ 𝑒) > π‘˜ for every edge 𝑒 ∈ 𝐸(Ξ“). collected in the next theorem. A graph Ξ“ is said to be goal-minimal of diameter π‘˜ or goal- minimally π‘˜-diametric (π‘˜-GMD for short), if the diameter Theorem 1. [14] of Ξ“ is equal to π‘˜, and for every edge 𝑒𝑣 ∈ 𝐸(Ξ“) the inequal- Let π‘˜ be a positive integer. A graph Ξ“ with order at least 3 ity π‘‘Ξ“βˆ’π‘’π‘£ (π‘₯, 𝑦) > π‘˜ holds if and only if {𝑒, 𝑣} = {π‘₯, 𝑦}. is π‘˜-GMD if and only if it has diameter π‘˜, girth π‘˜ + 2 and For an example of a GMD graph with diameter 3, see for any two non-adjacent vertices 𝑒 and 𝑣 there exist two Figure 1. internally-disjoint π‘’βˆ’π‘£ paths of length not exceeding π‘˜. Many of the π‘˜-GMD graphs have been discovered among the graphs belonging to the family of symmetric cubic graphs and among the cages. The symmetric cubic graphs are those cubic graphs, which are vertex-transitive and edge-transitive too. These graphs are collected into a catalogue, which can be found on the web site ([5]) of Marston Conder. We have Figure 1: A 3-GMD graph on 8 vertices. found thirty-six π‘˜-GMD graphs in this catalogue which are shown in Table 1. KyΕ‘ [16] conjectured that for every positive integer π‘˜ Conder ([4]) has constructed some cubic Cayley graphs there exists a π‘˜-GMD graph. He discovered such graphs in order to find minimal cubic graphs with prescribed only for π‘˜ = 1, 2, 3, 4, 6. Moreover, for π‘˜ = 1, 2, 4 he girth. Among them, we found two which fulfill the rela- gave infinite families of π‘˜-GMD graphs. In [19] PlesnΓ­k tion 𝑔 = π‘˜ + 2 from Theorem 1, where 𝑔 is the girth and showed the first examples of π‘˜-GMD graphs for diame- π‘˜ the diameter. It turns out that the first one is a 16-GMD ters π‘˜ = 5, 7, 8, 10, 12, 14, and constructed the first infinite graph and the second one is a 20-GMD graph. Conder in his paper did not specify the details of how to obtain the ITAT’22: Information technologies – Applications and Theory, Septem- generators of these Cayley graphs, but fortunately, his ber 23–27, 2022, Zuberec, Slovakia Envelope-Open stefan.gyurki@stuba.sk (Ε . GyΓΌrki) method was described by Biggs ([2]). Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). The construction of Cayley graphs in this paper is a CEUR Workshop Proceedings CEUR Workshop Proceedings (CEUR-WS.org) http://ceur-ws.org ISSN 1613-0073 slight generalization of the Conder’s method. graph result a power of a prime and the multiplicative group GFΓ— (π‘ž) C016.1 4-GMD is cyclic, so there exists a so-called primitive element C018.1 4-GMD (generator) πœ” of GF(π‘ž) such that C040.1 6-GMD C048.1 6-GMD GF(π‘ž) = {0, 1, πœ”, πœ” 2 , … , πœ” π‘žβˆ’2 }. C080.1 8-GMD For our aims it is sufficient to identify the finite field C090.1 8-GMD of prime order 𝑝 with the ℀𝑝 . Finite fields of order 𝑝 π‘˜ , C102.1 7-GMD where 𝑝 is a prime and π‘˜ β‰₯ 2, we can obtain by factoring C108.1 7-GMD the ring of polynomial over ℀𝑝 by an ideal generated by C128.2 8-GMD an irreducible polynomial 𝑃(π‘₯) of degree π‘˜. C144.2 8-GMD Let us consider the set 𝑇 = GF(π‘ž) βˆͺ {∞}. For each C224.3 10-GMD element 𝑔 ∈ GF(π‘ž) ⧡ {0, 1} define the mapping πœ‘π‘” ∢ 𝑇 β†’ 𝑇 C360.2 10-GMD by linear fractional transformation C364.3 10-GMD π‘₯ βˆ’1 C384.2 10-GMD πœ‘π‘” ∢ π‘₯ ↦ 𝑔π‘₯ βˆ’ 1 C384.3 10-GMD C440.3 10-GMD for π‘₯ βˆ‰ {𝑔 βˆ’1 , ∞}. Further, πœ‘π‘” (∞) = 𝑔 βˆ’1 and πœ‘π‘” (𝑔 βˆ’1 ) = ∞. C480.3 10-GMD It is easy to see that πœ‘π‘” is a permutation of 𝑇. Moreover, C512.1 12-GMD it is an involution, i.e. πœ‘π‘” = πœ‘π‘”βˆ’1 . From πœ‘π‘” one can derive C624.2 12-GMD many other permutations by the following. For every C672.7 12-GMD integer 1 ≀ 𝑛 ≀ π‘ž βˆ’ 2 define Φ𝑔,𝑛 ∢ 𝑇 β†’ 𝑇 as a conjuga- C768.3 12-GMD tion of πœ‘π‘” under the permutation π‘₯ ↦ πœ” 𝑛 π‘₯ in the group Sym(𝑇 ). Hence, we can use these mappings (involutions) C880.3 12-GMD to generate some undirected Cayley graphs. C912.2 12-GMD In fact, such permutations generate either the full C960.1 12-GMD group 𝑃𝑆𝐿(2, π‘ž) or some of its subgroup. C960.3 12-GMD C1008.2 12-GMD C1024.1 12-GMD 3. The construction C1092.3 12-GMD Conder constructed his graphs as cubic Cayley graphs C1140.3 12-GMD with generating set C1140.10 12-GMD C1344.5 12-GMD 𝑋 = {πœ‘π‘” , Φ𝑔,𝑛 , Φ𝑔,2𝑛 } (1) C1344.6 12-GMD C1632.7 14-GMD in the group 𝐺 = βŸ¨π‘‹ ⟩, where 𝑛 = (22π‘š βˆ’ 1)/3 for possible π‘š ∈ β„• and 𝑔 ∈ GF(π‘ž) ⧡ {0, 1}. C1792.8 14-GMD We have performed an exhaustive computer search for C2016.5 14-GMD arbitrary integers 1 ≀ π‘Ž < 𝑏 ≀ π‘ž βˆ’ 2 in the fields with up C2048.17 14-GMD to 49 element for generating sets 𝑋 of the form 𝑋 = {πœ‘π‘” , Φ𝑔,π‘Ž , Φ𝑔,𝑏 } (2) Table 1 π‘˜-GMD graphs from Conder’s catalogue. for every 𝑔 ∈ GF(π‘ž) ⧡ {0, 1}. Further, we explored the generating sets 𝑋 of the form (1) in the fields GF(π‘ž) for every possible π‘ž ≀ 103, where π‘ž ≑ 1 (mod 3). 2. Cayley graphs and finite fields Our computer search of these cases yielded more than 90 new π‘˜-GMD graphs. They are shown in Table 2. All Let 𝐺 be a finite group and 𝑋 be a subset of 𝐺 not con- these graphs are mutually non-isomorphic, since they taining the group identity and having the property that can be distinguished by the value of the total distance if β„Ž ∈ 𝑋 then β„Žβˆ’1 ∈ 𝑋. Then the Cayley graph of 𝐺 with in a graph. As one can see, these π‘˜-GMD graphs covers generating set 𝑋 is the graph 𝐢(𝐺, 𝑋 ) with vertex set 𝐺 diameters π‘˜ = 12, 16, 18, 19, 20, 21, 22, 23, 24 and 26. Thus, and vertices π‘₯ and 𝑦 are adjacent if and only if π‘₯𝑦 βˆ’1 ∈ 𝑋. we have found π‘˜-GMD graphs for nine new values of π‘˜. So Let GF(π‘ž) be the finite field with π‘ž elements. It is a at present there are known π‘˜-GMD graphs for 22 distinct well-known fact that such field exists if and only if π‘ž is values of π‘˜. The graphs were generated by the computer system GAP [8] and the goal-minimality property was [9] Gliviak F.: On certain edge critical graphs of given examined by a computer program based on the algorithm diameter, Mat. Časopis 25 (1975), 249–263. described in [15]. [10] Gliviak F., PlesnΓ­k J.: Some examples of goal- minimally 3-diametric graphs, J. Appl. Math. Stat. Example 1. The multiplicative group of GF(13) = Inform. 1 (2005), No. 2, 87–94. (β„€13 , βŠ•, βŠ™) is generated by 𝑔 = 2. If we take π‘Ž = 1 [11] Glivjak F.: On certain classes of graphs of diameter and 𝑏 = 2, then we get the following permutations of two without superfluous edges, Acta Fac. Rerum 𝑇 = β„€13 βˆͺ {∞}: Nat. Univ. Comenianae Math. 21 (1968), 39–48. [12] Glivjak F., KyΕ‘ P., PlesnΓ­k J.: On the extension of πœ‘2 = (0, 1)(3, 12)(4, 8)(6, 7)(9, 11)(10, ∞) graphs with a given diameter without superfluous Ξ¦2,1 = (0, 2)(1, 12)(3, 8)(5, 9)(6, 11)(7, ∞) edges, Mat. Časopis 19 (1969), No. 2, 92–101. Ξ¦2,2 = (0, 4)(1, ∞)(2, 11)(3, 6)(5, 10)(9, 12). [13] GyΓΌrki Ε .: Goal-minimally π‘˜-elongated graphs, Math. Slovaca 59 (2009), No. 2, 193–200. These permutations generate a subgroup Ξ“ of index 2 in [14] GyΓΌrki Ε .: Constructing goal-minimally π‘˜- 𝑃𝑆𝐿(2, 13), so |Ξ“| = 1092. The corresponding Cayley graph diametric graphs by lifts, Discrete Math. 312(2012), has diameter 12, girth 14 and it is a 12-GMD graph. This 3547–3552. graph is displayed in Table 2 under the number 1. [15] GyΓΌrki Ε ., MazΓ‘k J.: An efficient algorithm for test- ing goal-minimality of graphs, Discrete Appl. Math. We plan to continue in this search, but it requires too 161(2013), 1632–1634. much computer time. So we would like to know the [16] KyΕ‘ P.: Diameter strongly critical graphs, Acta answer to the next open question. Math. Univ. Comeniana 37 (1980), 71–83. Question. How to choose 𝑔 ∈ GF(π‘ž) and integers π‘Ž [17] KyΕ‘ P.: Diameter π‘˜-critical graphs, Acta Math. Univ. and 𝑏 in (2) in order to obtain a π‘˜-GMD graph for some Comeniana 38 (1981), 63–85. integer π‘˜? [18] PlesnΓ­k J.: Critical graphs of given diameter, Acta Fac. Rerum Nat. Univ. Comenianae Math. 30 (1975), 71–93. Acknowledgment [19] PlesnΓ­k J.: Examples of goal-minimally π‘˜-diametric graphs for some small values of π‘˜, Australas. J. Com- The author acknowledges support from the APVV Re- bin. 41 (2008), 93–105. search Grants 17-0428 and 19-0308, and from the VEGA Research Grants 1/0206/20 and 1/0567/22. The author would like to thank Martin Mačaj for valuable discussion on the subject. References [1] Anunchuen N., Caccetta L.: On strongly edge- critical graphs of given diameter, Australas. J. Com- bin. 8 (1993), 99–122. [2] Biggs N.: Constructions for cubic graphs with large girth, Electronic J. Combin. 5 (1998), A1. [3] Caccetta L., HΓ€ggkvist R.: On diameter critical graphs, Discrete Math. 28 (1979), 223–229. [4] Conder M.: Smallest trivalent graphs of large girth, Preprint, June 1997. [5] Conder M.: Trivalent (cubic) sym- metric graphs on up to 2048 vertices http://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt [6] Diestel R.: Graph Theory, third ed., Springer-Verlag, Heidelberg, 2005. [7] Fan G.: On diameter 2-critical graphs, Discrete Math. 67 (1987), 235–240. [8] GAP - Groups, Algorithms, Programming – a Sys- tem for Computational Discrete Algebra, www.gap- system.org . Table 2: π‘˜-GMD graphs obtained from finite fields. graph π‘ž 𝑔 π‘Ž 𝑏 order result |Aut| Total distance 1 13 πœ”2 1 2 1 092 12-GMD 2184 4784052 2 13 πœ”7 3 6 1 092 12-GMD 6552 4795518 3 16 πœ”3 5 10 4 080 16-GMD 24480 81753000 4 19 πœ”5 2 4 6 840 16-GMD 41040 252765360 5 19 πœ”5 2 10 6 840 16-GMD 13680 254352240 6 19 πœ”5 6 12 6 840 16-GMD 41040 251773560 7 25 πœ”4 8 16 7 800 16-GMD 46800 332853300 8 27 πœ”2 2 14 9 828 16-GMD 19656 540692334 9 29 πœ”3 2 8 12 180 16-GMD 24360 860906760 10 29 πœ”3 4 8 12 180 16-GMD 24360 853263810 11 29 πœ”6 1 13 12 180 16-GMD 24360 847100730 12 29 πœ”6 2 9 12 180 16-GMD 12180 851241930 13 29 πœ”6 4 9 12 180 16-GMD 24360 858708270 14 29 πœ”8 9 18 12 180 16-GMD 24360 857313660 15 29 πœ” 13 8 16 12 180 16-GMD 73080 856521960 16 31 πœ” 14 4 14 14 880 16-GMD 14880 1311828240 17 31 πœ” 17 2 14 29 760 18-GMD 29760 5777665920 18 32 πœ”3 7 16 32 736 18-GMD 32736 7024883712 19 32 πœ”5 1 16 32 736 18-GMD 65472 7002459552 20 32 πœ”5 2 4 32 736 18-GMD 65472 6949099872 21 32 πœ”5 8 18 32 736 18-GMD 32736 7046915040 22 32 πœ”7 3 12 32 736 18-GMD 32736 6986680800 23 32 πœ”7 7 15 32 736 18-GMD 32736 6958511472 24 32 πœ” 15 1 14 32 736 18-GMD 32736 6939573696 25 32 πœ” 15 3 6 32 736 18-GMD 65472 7024261728 26 32 πœ” 15 3 11 32 736 18-GMD 32736 7012296720 27 32 πœ” 15 5 12 32 736 18-GMD 32736 6987941136 28 37 πœ”2 10 22 25 308 18-GMD 25308 4065059538 29 37 πœ”2 12 24 25 308 18-GMD 151848 4052620656 30 37 πœ”5 12 24 50 616 20-GMD 303696 17698491792 31 37 πœ” 20 3 12 50 616 20-GMD 101232 17623731960 32 37 πœ” 25 12 24 50 616 20-GMD 33 37 πœ” 30 1 7 25 308 18-GMD 34 41 πœ” 6 19 34 440 18-GMD 35 41 πœ”3 3 15 34 440 18-GMD 36 41 πœ” 10 1 10 34 440 18-GMD 37 41 πœ” 16 6 12 68 880 20-GMD 38 41 πœ” 25 4 11 68 880 20-GMD 39 43 πœ”4 14 28 79 464 20-GMD 40 43 πœ”5 3 16 79 464 20-GMD 41 43 πœ”6 2 10 39 732 18-GMD 42 43 πœ”6 12 27 39 732 18-GMD 43 43 πœ”7 8 21 39 732 18-GMD 44 43 πœ”8 3 11 39 732 18-GMD 45 43 πœ”8 5 15 39 732 18-GMD 46 43 πœ” 10 4 14 39 732 18-GMD 47 43 πœ” 10 9 23 39 732 18-GMD 48 43 πœ” 10 12 24 39 732 18-GMD 49 43 πœ” 13 7 22 39 732 18-GMD The table continues on the next page. Table 2 – continuing from the previous page. graph π‘ž 𝑔 π‘Ž 𝑏 order result |Aut| Total distance 50 43 πœ” 13 9 20 39 732 18-GMD 51 43 πœ” 14 8 19 39 732 18-GMD 52 43 πœ” 17 4 17 39 732 18-GMD 53 43 πœ” 19 5 13 79 464 20-GMD 54 43 πœ” 21 11 23 39 732 18-GMD 55 43 πœ” 23 2 22 79 464 20-GMD 56 43 πœ” 24 1 7 39 732 18-GMD 57 43 πœ” 24 3 6 39 732 19-GMD 58 43 πœ” 24 3 16 39 732 18-GMD 59 43 πœ” 24 4 15 39 732 18-GMD 60 43 πœ” 24 5 10 39 732 18-GMD 61 43 πœ” 25 11 25 39 732 18-GMD 62 43 πœ” 27 3 19 39 732 18-GMD 63 43 πœ” 38 3 6 39 732 18-GMD 64 47 πœ”5 7 16 103 776 20-GMD 65 47 πœ” 11 3 12 51 888 19-GMD 66 47 πœ” 14 7 14 103 776 20-GMD 67 47 πœ” 16 13 26 51 888 20-GMD 68 47 πœ” 22 14 28 51 888 19-GMD 69 47 πœ” 37 4 18 103 776 20-GMD 70 49 πœ”2 16 32 58 800 19-GMD 71 49 πœ”3 2 19 58 800 19-GMD 72 49 πœ” 18 1 14 117 600 22-GMD 73 49 πœ” 20 6 21 117 600 20-GMD 74 61 πœ” 44 20 40 226 920 22-GMD 75 61 πœ” 53 20 40 226 920 22-GMD 76 64 πœ”1 21 42 262 080 23-GMD 77 64 πœ” 13 21 42 262 080 23-GMD 78 64 πœ” 23 21 42 262 080 23-GMD 79 64 πœ” 31 21 42 262 080 23-GMD 80 67 πœ” 13 22 44 150 348 22-GMD 81 67 πœ” 33 22 44 150 348 22-GMD 82 67 πœ” 59 22 44 150 348 22-GMD 83 73 πœ” 25 24 48 388 944 22-GMD 84 73 πœ” 37 24 48 194 472 22-GMD 85 73 πœ” 65 24 48 194 472 21-GMD 86 79 πœ” 62 26 52 246 480 22-GMD 87 79 πœ” 72 26 52 246 480 22-GMD 88 97 πœ”5 32 64 912 576 24-GMD 89 97 πœ”6 32 64 912 576 24-GMD 90 97 πœ” 41 32 64 456 288 23-GMD 91 97 πœ” 47 32 64 912 576 26-GMD 92 103 πœ”9 34 68 546 312 24-GMD 93 103 πœ” 50 34 68 1 092 624 26-GMD 94 103 πœ” 78 34 68 546 312 23-GMD 95 103 πœ” 93 34 68 546 312 24-GMD