Construction of directed strongly regular graphs with nontrivial automorphisms

Marija Maksimović, Sanja Rukavina · 2024

Read Construction of directed strongly regular graphs with nontrivial automorphisms by Marija Maksimović, Sanja Rukavina (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10901.txt.

Introduction

Marija Maksimović and Sanja Rukavina build rare network patterns with the help of symmetry, in a 2024 paper. The patterns are directed graphs where each node links to a set count of others, and pairs of nodes share counts that depend only on how they relate. Such tight balance makes them prized in network math, yet hard to find. Their method assumes a symmetry group acts on the graph, which cuts the search space.

The method yields the first graphs of one wanted kind, sized at 22 nodes with a set link pattern. The team proves that a prime-order symmetry on such a graph can only be of order two or three. They built 472 graphs of the kind and sorted all the ones that carry the order-three symmetry. The work opens a shelf of examples where none stood before.

Catalog record

CREATORMarija Maksimović, Sanja Rukavina
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-10901

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Construction of directed strongly regular graphs with nontrivial automorphisms Marija Maksimović, Sanja Rukavina Abstract In this paper we present a method for constructing directed strongly regular graphs with assumed action of an automorphism group. The application of this method leads to first examples of directed strongly regular graphs with parameters ( 22 , 9 , 6 , 3 , 4 ) (22,9,6,3,4) . We have shown that an automorphism of prime order acting on such a graph can only be of order two or three. Furthermore, we have constructed 472 472 directed strongly regular graphs with parameters ( 22 , 9 , 6 , 3 , 4 ) (22,9,6,3,4) and classified all these graphs with an automorphism of order three. Keywords: directed graph, strongly regular graph, automorphism group Mathematical subject classification (2020): 05C20, 05E18, 05E30 1 Introduction We assume familiarity with the basic facts and concepts of graph theory. For further reading on the topic, we refer the reader to [ 2 , 4 , 8 ] . In [ 8 ] Duval introduced the directed graph version of a strongly regular graph. A directed graph is a pair \Gamma=(V,E) consisting of a set V , referred to as the vertex set of \Gamma and a set E\subseteq V\times V , which is called the edge set of \Gamma . A directed strongly regular graph with parameters (v,k,t,\lambda,\mu) is a directed graph \Gamma=(V,E) on v vertices without loops such that each vertex x\in V has in-degree and out-degree k , each vertex x\in V has t out-neighbors that are also in-neighbors of x , and for each pair of vertices x,y\in V , the number of directed paths of length two from x to y is \lambda if (x,y)\in E , and \mu if (x,y)\notin E . We call such a graph \Gamma a DSRG(v,k,t,\lambda,\mu). Its adjacency matrix A=[a_{ij}] is a (0,1) -matrix with rows and columns indexed by V and defined by a_{xy}=1 if and only if (x,y)\in E . The adjacency matrix A of \Gamma satisfies \displaystyle A^{2}+(\mu-\lambda)A-(t-\mu)I=\mu J (1.0.1) \displaystyle AJ=JA=kJ (1.0.2) where I denotes the identity matrix and J the all-1 matrix of order v . Since the introduction of directed strongly regular graphs by Duval [ 8 ] , this concept has attracted the attention of many researchers. An overview of the known results and parameters for which such graphs have been constructed is presented in [ 3 ] . According to [ 3 ] , the smallest open case of admissible parameters for which the existence of a directed strongly regular graph has not been proved is (22,9,6,3,4) . We have not found an example of such a graph in the literature either. In this paper we give a method for the construction of directed strongly regular graphs with presumed action of an automorphism group by adapting the method used for the construction of other types of incidence structures, including strongly regular graphs (see [ 1 , 5 ] ). The method is based on a construction of orbit matrices, which are then refined to obtain the adjacency matrix of a directed strongly regular graph. The work is structured as follows. After describing the basic properties of orbit matrices of directed strongly regular graphs and introducing the notation in Section 2 , a method for constructing directed strongly regular graphs from their orbit matrices is presented in Section 3 . By applying the developed method to a construction of directed strongly regular graphs with parameters (22,9,6,3,4) , we constructed 472 nonisomorphic graphs in Section 4 . These are the first examples of directed strongly regular graphs with parameters (22,9,6,3,4) . Moreover, we show that an automorphism of prime order acting on such a graph can only be of order two or three, and classify all DSRGs (22,9,6,3,4) with an automorphism of order three. Our results are summarized in Section 5 . The orbit matrices and directed strongly regular graphs constructed in this paper were constructed and analyzed using GAP [ 10 ] . 2 Orbit matrices of directed strongly regular graphs Orbit matrices of strongly regular graphs have been considered in [ 1 , 5 ] . The definition and some properties of orbit matrices of directed strongly regular graphs can be found in [ 7 ] , where orbit matrices of known directed strongly regular graphs were used to construct new directed strongly regular graphs with prescribed automorphism group using a genetic algorithm. Our goal is to adapt the method used for the construction of other types of incidence structures (see, for example, [ 1 , 5 , 6 , 9 ] ) and to construct matrices corresponding to the definition of orbit matrices of directed strongly regular graphs, which are then used for the construction of all nonisomorphic directed strongly regular graphs resulting from the obtained matrices. Thus, in this section we give an overview of the basic facts and properties of orbit matrices that we need for our construction and introduce the notation for the rest of the paper. Let \Gamma=(V,E) be a DSRG (v,k,t,\lambda,\mu) , and let A be its adjacency matrix. An automorphism of \Gamma is a permutation \sigma of the vertex set V such that, for every pair of vertices x,y\in V , (x,y)\in E if and only if (\sigma(x),\sigma(y))\in E . The set of all automorphisms of \Gamma forms a group under composition called the full automorphism group of \Gamma and denoted by Aut(\Gamma) . Suppose an automorphism group G of \Gamma partitions the vertex set V into b orbits O_{1},O_{2},\dots,O_{b} with corresponding sizes n_{1},n_{2},\dots,n_{b} , respectively. The adjacency matrix A can be subdivided into submatrices [A_{ij}] , where A_{ij} represents the submatrix whose rows and columns are indexed by elements of O_{i} and O_{j} , respectively. Define two matrices C=[c_{ij}] and R=[r_{ij}] for 1\leq i,j\leq b , such that: c_{ij}=\text{column sum of }A_{ij},\quad r_{ij}=\text{row sum of }A_{ij}. C is the column orbit matrix of \Gamma with respect to the group G , and R is the row orbit matrix of \Gamma with respect to the group G . The matrices C and R are connected by the following equation: \displaystyle r_{ij}n_{i}=c_{ij}n_{j}. (2.0.1) Let W=A^{2} . Using the same partitioning of the vertex set V into orbits, the matrix W can be partitioned as W=[W_{ij}] , where i and j are the indices of the orbits. Finally, let N=\text{diag}(n_{1},n_{2},\dots,n_{b}) and define a b\times b matrix S=[s_{ij}] , where s_{ij} is equal to the sum of all entries in W_{ij} . The following result will be useful. Proposition 2.1 . With reference to the above notations, the following holds: CNR=S. Proof. Let \alpha_{i} be a vector of size v such that \alpha_{i}(j)=\begin{cases}1,\quad j\in O_{i}\\ 0,\quad j\notin O_{i}\end{cases}. Then we have s_{ij}=\alpha_{i}A^{2}\alpha_{j}^{T}=(\alpha_{i}A)(A\alpha_{j}^{T})=\sum_{z=1}^{b}c_{iz}r_{zj}n_{z}=(CNR)_{ij}. ∎ From ( 1.0.1 ) it follows that W_{ij}=\delta_{ij}(t-\mu)I+\mu J+(\lambda-\mu)A_{ij} , and therefore \displaystyle s_{ij}= \displaystyle\delta_{ij}(t-\mu)n_{j}+\mu n_{i}n_{j}+(\lambda-\mu)c_{ij}n_{j} \displaystyle= \displaystyle\delta_{ij}(t-\mu)n_{i}+\mu n_{i}n_{j}+(\lambda-\mu)r_{ij}n_{i}. Furthermore, from ( 2.0.1 ) and Proposition 2.1 we have s_{ij}=\sum_{z=1}^{b}c_{iz}r_{zj}n_{z}=\sum_{z=1}^{b}c_{iz}c_{zj}n_{j}=\sum_{z=1}^{b}r_{iz}r_{zj}n_{i}. It follows that the elements of the column orbit matrix C fulfil the following conditions \delta_{ij}(t-\mu)n_{j}+\mu n_{i}n_{j}+(\lambda-\mu)c_{ij}n_{j}=\sum_{z=1}^{b}c_{iz}c_{zj}n_{j}, that is \delta_{ij}(t-\mu)+\mu n_{i}+(\lambda-\mu)c_{ij}=\sum_{z=1}^{b}c_{iz}c_{zj}, while for the elements of the row orbit matrix R applies in a similar way \delta_{ij}(t-\mu)+\mu n_{j}+(\lambda-\mu)r_{ij}=\sum_{z=1}^{b}r_{iz}r_{zj}. Therefore, we introduce the following definitions of the

Read the complete text