A Siamese color graph is an edge decomposition of a complete graph into strongly regular subgraphs sharing a spread. Using a computer aided exhaustive search we completely classify so called geometric Siamese color graphs on 40 vertices. We also independently confirm the classifications of Siamese color graphs on 15 vertices originally obtained by M. Klin, S. Reichard, and A. Woldar. One of the objects related to an incidence structure is its point graph (or collinearity graph). It is a graph whose Siamese color graphs were initially introduced by vertices are the points of the incidence structure and two Kharaghani and Torabi in [1] using algebraic meth- vertices are connected by an edge if and only if they lay ods and later studied by Klin, Reichard, and Woldar in on the same line. [2, 3] from the geometric point of view. Kharaghani A strongly regular graph with parameters (, , , ) and Torabi provided an infinite class of Siamese color is a regular graph with order and valency 0 < < graphs arising from an infinite class of balanced gen- − 1 such that every pair of adjacent vertices in Γ have eralized weighing matrices supplied by Gibbons and common neighbours, and every pair of non-adjacent Mathon in [4]. Klin, Reichard, and Woldar presented vertices have common neighbours. a complete list of Siamese color graphs on 15 vertices It is easy to show, that the point graph of any partial and some geometric Siamese color graphs on 40 ver- geometry is strongly regular with parameters tices [2, 3]. Most results obtained so far concern Siamese color graph with strongly regular graphs with parame- = ((− 1)(− 1)/ + 1) , ters (1 + + 2 + 3, 2 + , − 1 + , 1 + , ). Such = ( − 1), graphs are pseudo-geometric with respect to generalised quadrangles of order and are known to exist for all = ( − 2) + ( − 1)( − 1), prime powers. = .
2. Preliminaries point graph of a suitable partial geometry, it is said to be geometric and if its parameter set coincides with that of 2.1. Partial geometries and strongly a geometric strongly regular graph, it is called pseudoregular graphs geometric.
A spread of a partial geometry is a set of pairwise A partial geometry is an incidence structure with parame- disjoint lines that together contain all the points of the ters (, , ) such that each block (or line) contains geometry. points, each point lays on lines, each pair of distinct Since a spread divides ((− 1)(− 1)/ + 1) points of points lay on at most one line, and for each line and the partial geometry into mutually disjoint sets of point not on , there exist exactly lines through points, there are (− 1)(− 1)/ + 1 lines in one spread. that intersect . Any two points on the same line in the spread must be
By double-counting, it is easy to see that any such adjacent in the point graph, therefore all points belonging structure has (( − 1)( − 1)/ + 1) points and to the same line in the spread form a clique in the point (( − 1)( − 1)/ + 1) lines. graph. If we have a spread of a partial geometry, it spans the set of points by (− 1)(− 1) + 1 lines, therefore, in IbTeArT2’32–32:7I,n2fo0r2m2,aVtiyosnokteécThantorlyo,gSielosv–akAipaplications and Theory, Septem- the point graph, there is a set of (− 1)(− 1) + 1 = $ nina.hronkovicova@fmph.uniba.sk (N. Hronkovičová); cliques of size . In accordance, if we have any graph Γ martin.macaj@fmph.uniba.sk (M. Mačaj) with disjoint set of same-size cliques that span the whole © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Γ , we shall call it a spread in Γ .
CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org)
Let there be a spread in a partial geometry with parameters (, , ), let , be distinct lines of , for any point on , there are exactly lines through that intersect through diferent points. Similarly, for any point on , there are exactly lines through that intersect through diferent points. Therefore there are exactly diferent lines that intersect both and , and they do so in pair-wise diferent pairs of points on and .
cliques in the spread are connected by exactly 1 + edges, that is, a perfect matching. This can be expressed as follows.
Lemma 2. If we arrange the vertices of the point graph of (, ) with a spread according to their corresponding cliques, the resulting adjacency matrix can be represented by (1 + ) × (1 + ) blocks with each block of size of (1 + ) × (1 + ). The diagonal blocks of the matrix correspond to the adjacency matrices of the cliques, i.e. − , while the of-diagonal blocks correspond to permutation matrices, that is, the incidence matrices of 1-factors.
is an incidence structure satisfying the following axioms:
Given a Γ with diameter , Γ is a distance-regular graph if and only if there is an array of integers {0, 1, . . . , − 1; 1, 2, . . . , } such that for all 1 ≤ ≤ , and any pair of vertices and at a distance in Γ , gives the number of neighbours of at distance 1. Each point is incident with + 1 lines ( ≥ 1) and + 1 from and gives the number of neighbours two distinct points are incident with at most one of at a distance − 1 from . The array of integers line. characterising a distance-regular graph is known as its 2. Each line is incident with + 1 points ( ≥ 1) intersection array.
and two distinct lines are incident with at most It was shown by Brouwer in [5] that the removal of a one point. spread from a pseudo-geometric or geometric strongly regular graph Γ with a spread and parameters coinciding 3. If is a point and is a line not incident with , to parameters of the point graph of (, ) gives us then there exists exactly one line through that a distance-regular graph of diameter 3 with antipodal intersects . system , that is, the relation of being at distance 3 in distance-regular graph Γ − is an equivalence relation and its blocks are exactly the cliques of .
If the strongly regular graph Γ is geometric, we shall call the distance-regular graph Γ − geometric as well. 2.2. Siamese color graphs
will refer to a generalized quadrangle of order (, ) as (, ).
It is straightforward to show that generalised quadrangles are a particular case of partial geometries. In particular, the generalised quadrangles of orders (, ) are exactly the partial geometries with parameters ( + 1, + 1, 1).
Hence, the point graph of a generalised quadrangle of order (, ) is a strongly regular graph with parameters (, , , ), where A color graph Γ is a pair (, ℛ) where is a set of vertices and ℛ is a partition of 2, i.e., elements of ℛ are pairwise disjoint and ⋃︀∈ℛ = 2. We refer to the relations in ℛ as the colors of Γ and to the number |ℛ| of its colors as the rank of Γ . = ( + 1)( + 1), In other words, a color graph is any edge-coloring of a complete digraph with a loop at each vertex. We = ( + 1), define an adjacency matrix of a color graph to be a × = − 1, matrix = (, ) such that , = if (, ) ∈ = + 1. for ∈ ℛ.
Throughout this paper we will only consider color
Every line in (, ) gives rise to a clique of size graphs such that all their colors are symmetric relations 1 + in the point graph. On the other hand, there are no and one of them is an identity relation, i.e., ones that can other cliques as the third condition in the definition of be restricted to a simple graph, not a digraph. generalized quadrangles tells us that every three points Let Γ and Γ ′ be color graphs. An isomorphism : that induce a 3 in the point graph must belong to the Γ → Γ ′ is a bijection of onto ′ which induces a same line. bijection : ℛ → ℛ′ of colors. A weak (or color)
Incidentally, there is a one-to-one correspondence be- automorphism of Γ is an isomorphism : Γ → Γ . If, in tween spreads in (, ) and those spreads in its point addition, the induced map is the identity on ℛ, we call graph which consist of (1 + ) cliques of size 1 + . a (strong) automorphism of Γ .
the authors constructed an infinite family of geometric concept of a Siamese color graph, i.e., the decomposition
of a complete graph into strongly regular graphs sharphic to the family of Kharabhani and Torabi and proved ing a spread. This notion is formalised in the following the following result.
Let = (, { , , 1, 2, . . . , }) of order . For each point graph (, ∪ ), construct the definition.
Definition 1. be a color graph for which size.
.
regular graph of diameter 3 with antipodal system graph with the same parameters.
3. For all , graph (, ∪ ) is a strongly regular
Γ and – the number of distance-regular graphs – the
We shall denote by (, , , , ) where (, , ,
) are common parameters of all (, ∪ ) and is the valency of the spread . Kharaghani and
these strongly regular graphs share a common spread.
Theorem 1. For any prime power , there exists a (1 + + is a SCG on 1 + + 2 + 3, + 2, − 1 + , 1 + , ), that
2 + 3 vertices consisting of 1 + strongly regular graphs sharing 1 + 2 disjoint cliques of size 1 + .
Parameters of strongly regular graphs mentioned above are interesting because these are the parameters of a point graph of generalised quadrangle (, ). In the following we will refer to Siamese color graphs with these parameters as Siamese color graphs of order and denote them (). By the Theorem of Brouwer [5] mentioned after the definition of distance-regular graphs, for this class of Siamese color graphs, we do not have to check the second condition in Definition 1 if the remaining two are fulfilled.
if all its strongly regular graphs (, ∪) are geometric.
is a Steiner design = (, ) ︂( = 2, + 1, 4 − 1 )︂ − 1 .
pletely classified Siamese color graphs of order 2 and found hundreds of geometric Siamese color graphs of order 3. The classification of Siamese color graphs of order 2 was expressed in the following theorem.
Our primary emphasis in the search was on Siamese color graphs of order 3, although we also examined the case for order 2, which represents the smallest non-trivial scenario. To begin with, we shall summarize the established information regarding the Siamese color graphs of order
Siamese color graphs or order 2
• The spread consists of five 3
• The strongly regulars graphs have parameters
(
Furthermore, we have chosen the graph Γ 1 with lexi– one is not geometric and it has two non- cographically maximal adjacency matrix 1. As a conisomorphic spreads sequence, all blocks in the first row of the block form of 1 are equal to the identity matrix. • The distance-regular graphs have intersection ar- Step 2: rays {9, 6, 1; 1; 2; 9}. There are three of them and As is the antipodal system of Γ 1 we have = only one is geometric (Γ 1) ≤ () and it sufices to apply representatives of the cosets of in () to Γ 1. Moreover, we 4.1. Computer-aided search for geometric used the action of () = 4 ≀ 10 = (410 ⋊ 10) Siamese color graphs of orders 2 and on cliques of to implement an intelligent backtrack on 3 each coset of 410.
Step 3:
Our goal is to obtain the set () of all mutually non- As blocks in the first row of Γ 1 are all identity matrices,
isomorphic geometric Siamese color graphs of order for there are only nine permutation matrices disjoint with
∈ {2, 3}. It follows that for ≤ 3 and for a fixed spread any of them and there are only four combinations of
all geometric distance regular graphs with antipodal any three of these matrices and identity matrix such that
system form a single orbit of (). Therefore, the they are disjoint and their sum is an all-ones matrix. We
following four-step strategy is suficient to obtain (). distributed the computations in such a way that in each
instance we restricted the candidates for Γ 2, Γ 3, and Γ 4
1. For a fixed spread , choose a geometric distance to graphs with prescribed first three blocks of the first
regular graph Γ 1 with the antipodal system row of the block form of the adjacency matrix.
(i.e., Γ 1 + is the point graph of (
• binary numbers generated by concatenation of parts of rows of the full adjacency matrix that belong to the blocks above the diagonal blocks –
Steps 2 and 3
color graphs of order 3 the graph Γ 2 is the element with • their adjacency matrices in the block form, where the largest adjacency matrix in the set above. We will every permutation matrix is represented by num- further refer to this subset as ′. ber in {1, 2, . . . , 24} and − by 0 – Steps 1, 2 For each of the 399 geometric Siamese color graphs and 4 of order 3, we computed its automorphism group and its
[10], and GAP packages GRAPE and DESIGN [11, 12].
For = 2 the literal implementations of the strategy was
suficient to obtain the set (
Step 1: We fixed the spread with cliques {1, . . . , 4}, {5, . . . , 8}, . . . , {37, . . . , 40}. This choice of enabled us to represent our graphs during the computation by any of the following
For = 2 we confirmed the results of Klin, Reichard, and Woldar that there are only two Siamese color graphs of order 2.
For = 3 we obtained the following result.
orbit on vertices. Further, in accordance with Theorem 2, we computed the corresponding Steiner system, its automorphism group as well as its orbits on the points and the blocks. The results are compiled in the table below. The last column tells us, how many out of all of these non-isomorphic Siamese color graphs come from ′.