with not so small diameters

Abstract

using Cayley graphs with generators obtained by linear fractional transformations on the set of elements of a finite field

-

Γ−

(, ) > 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 dificult 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 GF() extended by an element ∞. 1. Introduction Minimal graphs with respect to diameter were studied by many authors, for example see [ 1 ], [ 3 ], [ 7 ], [ 9 ], [ 11 ], [ 12 ], [ 17 ] and [ 18 ]. A special subclass of this class of graphs are so-called goal-minimal graphs with respect to diameter which were introduced by Kyš in [ 16 ] and studied by Gliviak and Plesník in [ 10 ], [ 19 ] and by Gyürki in [ 13 ] and [ 14 ].

A graph Γ with diameter is called a minimal graph A graph Γ is said to be goal-minimal of diameter or goalminimally -diametric ( -GMD for short), if the diameter of Γ is equal to , and for every edge ∈ (Γ)

the inequality Γ−

(, ) >

holds if and only if {, } = {, }

.

For an example of a GMD graph with diameter 3, see

Kyš [ 16 ] conjectured that for every positive integer there exists a -GMD graph. He discovered such graphs only for = 1, 2, 3, 4, 6 . Moreover, for = 1, 2, 4

he gave infinite families of -GMD graphs. In [ 19 ] Plesník ters = 5, 7, 8, 10, 12, 14 , and constructed the first infinite ITAT’22: Information technologies – Applications and Theory, September 23–27, 2022, Zuberec, Slovakia nEvelop-O © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License

family of 6-GMD graphs. Gyürki [ 14 ] constructed by lifts the first known 9-GMD and 13-GMD graphs, moreover, he found an infinite family of 5-GMD graphs. Thus, before our research such graphs have been known only for values ≤ 14 , except of the case = 11 .

In this paper we construct -GMD graphs as Cayley graphs with generating set obtained from linear fractional transformations on GF() ∪ {∞} , having larger diameters.

The most important properties of -GMD graphs are Theorem 1. [ 14 ]

Let be a positive integer. A graph Γ with order at least 3 is -GMD if and only if it has diameter , girth + 2 and for any two non-adjacent vertices and there exist two 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 found thirty-six -GMD graphs in this catalogue which are shown in Table 1.

Conder ([ 4 ]) has constructed some cubic Cayley graphs in order to find minimal cubic graphs with prescribed girth. Among them, we found two which fulfill the relation = + 2

from Theorem 1, where is the girth and graph and the second one is a 20-GMD graph. Conder in his paper did not specify the details of how to obtain the generators of these Cayley graphs, but fortunately, his method was described by Biggs ([ 2 ]).

The construction of Cayley graphs in this paper is a slight generalization of the Conder’s method. showed the first examples of -GMD graphs for diame- the diameter. It turns out that the first one is a 16-GMD graph C016.1 C018.1 C040.1 C048.1 C080.1 C090.1 C102.1 C108.1 C128.2 C144.2 C224.3 C360.2 C364.3 C384.2 C384.3 C440.3 C480.3 C512.1 C624.2 C672.7 C768.3 C880.3 C912.2 C960.1 C960.3 C1008.2 C1024.1 C1092.3 C1140.3 C1140.10 C1344.5 C1344.6 C1632.7 C1792.8 C2016.5 C2048.17 4-GMD 4-GMD 6-GMD 6-GMD 8-GMD 8-GMD 7-GMD 7-GMD 8-GMD 8-GMD 10-GMD 10-GMD 10-GMD 10-GMD 10-GMD 10-GMD 10-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 12-GMD 14-GMD 14-GMD 14-GMD 14-GMD 2. Cayley graphs and finite fields a power of a prime and the multiplicative group GF×() is cyclic, so there exists a so-called primitive element (generator) of GF() such that

GF() = {0, 1, ,

2, … , −2 }.

For our aims it is suficient to identify the finite field an irreducible polynomial ()

of degree . of prime order with the ℤ . Finite fields of order ,

where is a prime and ≥ 2 , we can obtain by factoring the ring of polynomial over ℤ by an ideal generated by

Let us consider the set =

GF() ∪ {∞} . For each element ∈

GF() ⧵ {0, 1} define the mapping ∶ → by linear fractional transformation ∶ ↦ − 1 − 1 for ∉ { −1, ∞}. Further, (∞) = −1 and ( −1) = ∞.

It is easy to see that is a permutation of . Moreover, it is an involution, i.e. = −1. From one can derive many other permutations by the following. For every integer 1 ≤ ≤ − 2

define tion of under the permutation ↦ Φ, ∶ → as a conjuga in the group Sym( ) . Hence, we can use these mappings (involutions) to generate some undirected Cayley graphs.

In fact, such permutations generate either the full group (2, )

or some of its subgroup. 3. The construction Conder constructed his graphs as cubic Cayley graphs with generating set

= { , Φ, , Φ,2 } in the group = ⟨ ⟩ ∈ ℕ and ∈

GF() ⧵ {0, 1} .

We have performed an exhaustive computer search for arbitrary integers 1 ≤ < ≤ − 2

in the fields with up to 49 element for generating sets of the form

, where = (2 2 − 1)/3 for possible = { , Φ, , Φ, } for every ∈

GF() ⧵ {0, 1} . Further, we explored the generating sets of the form (1) in the fields every possible ≤ 103 , where ≡ 1 ( mod 3).

GF() for

Our computer search of these cases yielded more than 90 new -GMD graphs. They are shown in Table 2. All (1) (2) taining the group identity and having the property that well-known fact that such field exists if and only if is can be distinguished by the value of the total distance in a graph. As one can see, these -GMD graphs covers diameters = 12, 16, 18, 19, 20, 21, 22, 23, 24 and 26. Thus, we have found -GMD graphs for nine new values of . So at present there are known -GMD graphs for 22 distinct values of . The graphs were generated by the computer system GAP [ 8 ] and the goal-minimality property was examined by a computer program based on the algorithm described in [ 15 ].

We plan to continue in this search, but it requires too much computer time. So we would like to know the answer to the next open question.

Question. How to choose ∈ GF() and integers and in (2) in order to obtain a -GMD graph for some integer ? Acknowledgment The author acknowledges support from the APVV Research 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. graph order

The table continues on the next page. 34 graph order

References

[9] Gliviak F. : On certain edge critical graphs of given diameter , Mat. Časopis 25 ( 1975 ), 249 - 263 .

[10] Gliviak F. , Plesník J.: Some examples of goalminimally 3-diametric graphs , J. Appl. Math. Stat. Inform . 1 ( 2005 ), No. 2 , 87 - 94 .

[11] Glivjak F. : On certain classes of graphs of diameter two without superfluous edges , Acta Fac. Rerum Nat. Univ. Comenianae Math . 21 ( 1968 ), 39 - 48 .

[12] Glivjak F. , Kyš P. , Plesník J .: On the extension of graphs with a given diameter without superfluous edges , Mat. Časopis 19 ( 1969 ), No. 2 , 92 - 101 .

[13] Gyürki Š. : Goal-minimally -elongated graphs , Math. Slovaca 59 ( 2009 ), No. 2 , 193 - 200 .

[14] Gyürki Š. : Constructing goal-minimally - diametric graphs by lifts , Discrete Math. 312 ( 2012 ), 3547 - 3552 .

[15] Gyürki Š. , Mazák J.: An eficient algorithm for testing goal-minimality of graphs, Discrete Appl . Math. 161 ( 2013 ), 1632 - 1634 .

[16] Kyš P. : Diameter strongly critical graphs , Acta Math. Univ. Comeniana 37 ( 1980 ), 71 - 83 .

[17] Kyš P. : Diameter -critical graphs , Acta Math. Univ. Comeniana 38 ( 1981 ), 63 - 85 .

[18] Plesník J.: Critical graphs of given diameter , Acta Fac. Rerum Nat. Univ. Comenianae Math . 30 ( 1975 ), 71 - 93 .

[19] Plesník J.: Examples of goal-minimally -diametric graphs for some small values of , Australas. J. Combin . 41 ( 2008 ), 93 - 105 .

[1] Anunchuen N. , Caccetta L. : On strongly edgecritical graphs of given diameter , Australas. J. Combin . 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) symmetric 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 System for Computational Discrete Algebra, www .gapsystem.org.