<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta>
      <issn pub-type="ppub">1613-0073</issn>
    </journal-meta>
    <article-meta>
      <contrib-group>
        <contrib contrib-type="author">
          <string-name>Nina Hronkovičová</string-name>
          <email>nina.hronkovicova@fmph.uniba.sk</email>
          <xref ref-type="aff" rid="aff0">0</xref>
          <xref ref-type="aff" rid="aff1">1</xref>
        </contrib>
        <contrib contrib-type="author">
          <string-name>Martin Mačaj</string-name>
          <email>martin.macaj@fmph.uniba.sk</email>
          <xref ref-type="aff" rid="aff0">0</xref>
          <xref ref-type="aff" rid="aff1">1</xref>
        </contrib>
        <contrib contrib-type="editor">
          <string-name>Bratislava, Slovakia</string-name>
        </contrib>
        <aff id="aff0">
          <label>0</label>
          <institution>Department of Algebra and Geometry, Faculty of Mathematics</institution>
          ,
          <addr-line>Physics and Informatics</addr-line>
          ,
          <institution>Comenius University</institution>
          ,
          <addr-line>Mlynská Dolina 824 48</addr-line>
        </aff>
        <aff id="aff1">
          <label>1</label>
          <institution>ITAT'24: Information technologies - Applications and Theory</institution>
          ,
          <country country="SK">Slovakia</country>
        </aff>
      </contrib-group>
      <abstract>
        <p>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 complete the classification of Siamese color graphs on Siamese color graphs, graph decompositions, generalized quadrangles, strongly regular graphs ing matrices supplied by Gibbons and Mathon in [4]. partial geometry is strongly regular with parameters:</p>
      </abstract>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>-</title>
      <p>CEUR
ceur-ws.org</p>
    </sec>
    <sec id="sec-2">
      <title>1. Introduction</title>
      <sec id="sec-2-1">
        <title>Siamese color graphs were initially introduced by</title>
      </sec>
      <sec id="sec-2-2">
        <title>Kharaghani and Torabi in [1] using algebraic methods</title>
        <p>
          and later studied by Klin, Reichard, and Woldar in [
          <xref ref-type="bibr" rid="ref2 ref3">2, 3</xref>
          ]
from the geometric point of view. Kharaghani and Torabi
provided an infinite class of Siamese color graphs
arising from an infinite class of balanced generalized
weigh
        </p>
      </sec>
      <sec id="sec-2-3">
        <title>Klin, Reichard, and Woldar presented a complete list of</title>
      </sec>
      <sec id="sec-2-4">
        <title>Siamese color graphs on 15 vertices and some geometric</title>
        <p>
          Siamese color graphs on 40 vertices [
          <xref ref-type="bibr" rid="ref2 ref3">2, 3</xref>
          ]. Last year we
completed the classification of geometric Siamese color
graphs on 40 vertices in [
          <xref ref-type="bibr" rid="ref5">5</xref>
          ]. Our current aim is to classify
the pseudo-geometric and mixed cases, thereby complete
the classification of Siamese color graphs on 40 vertices.
        </p>
      </sec>
    </sec>
    <sec id="sec-3">
      <title>2. Preliminaries</title>
      <sec id="sec-3-1">
        <title>2.1. Partial geometries and strongly regular graphs</title>
        <sec id="sec-3-1-1">
          <title>A partial geometry is defined as an incidence structure</title>
          <p>characterized by the parameters (, ,  ). In this
structure, each block (or line) includes  points, each point
is on  lines, any pair of distinct points lies on at most
one line, and for any line  and point  not on , there are
exactly  lines through  that intersect .</p>
        </sec>
        <sec id="sec-3-1-2">
          <title>By employing double-counting, it becomes evident</title>
          <p>points and  ((− 1)(− 1)/ + 1) lines.</p>
        </sec>
        <sec id="sec-3-1-3">
          <title>A related concept to an incidence structure is its point</title>
          <p>graph (or collinearity graph), which vertices represent the
points of the incidence structure, and two vertices are</p>
          <p>CEUR
Workshop
Proce dings
htp:/ceur-ws.org
ISN1613-073</p>
          <p>CEUR</p>
          <p>Workshop Proceedings (CEUR-WS.org)
connected by an edge if and only if they lie on the same
line.</p>
          <p>A strongly regular graph with parameters (, , ,  )
is defined as a regular graph with order  and valency
0 &lt;  &lt;  −</p>
        </sec>
        <sec id="sec-3-1-4">
          <title>1, where each pair of adjacent vertices</title>
          <p>has  common neighbors, and each pair of non-adjacent
vertices has  common neighbors.</p>
          <p>It can be demonstrated that the point graph of any
 = 
︂( ( − 1)( − 1)</p>
          <p>︂)
+ 1 ,

 = ( − 1),
 = ( − 2) + ( − 1)( − 1),
 =  .</p>
        </sec>
        <sec id="sec-3-1-5">
          <title>Conversely, a strongly regular graph that is the point</title>
          <p>graph of a suitable partial geometry is termed geometric.</p>
        </sec>
        <sec id="sec-3-1-6">
          <title>The pseudo-geometric strongly regular graph has the same</title>
          <p>parameter set as a geometric one, but does not come as a
point graph of a given partial geometry.</p>
        </sec>
        <sec id="sec-3-1-7">
          <title>A spread in a partial geometry is a set of pair</title>
          <p>wise disjoint lines that collectively cover all the
points of the geometry.</p>
        </sec>
        <sec id="sec-3-1-8">
          <title>Since a spread partitions</title>
          <p>the  ((− 1)(− 1)/ + 1) points of the partial
geometry into disjoint sets of  points, there are
((− 1)(− 1)/ +1)/ lines in a spread.</p>
        </sec>
        <sec id="sec-3-1-9">
          <title>In the point graph, any two points on the same line in</title>
          <p>the spread are adjacent, thus forming a clique. If a spread
set into  cliques of size . Consequently, any graph
 with a disjoint set of equal-sized cliques spanning 
is said to have a spread.</p>
          <p>Consider a spread  in a partial geometry with
parameters (, ,  ). For any distinct lines  and  in , and
any point  on , exactly  lines through  intersect 
at  distinct points. Similarly, for any point  on ,
exactly  lines through  intersect  at  distinct points.
intersecting in distinct pairs of points on  and .
that such a structure comprises  ((− 1)(− 1)/ + 1) is present in a partial geometry, it partitions the point
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Therefore, precisely  lines intersect both  and ,</p>
        </sec>
        <sec id="sec-3-1-10">
          <title>3. For any point  and line  not incident with ,</title>
          <p>there is exactly one line through  that intersects
.</p>
          <p>A (finite) generalized quadrangle with parameters (, )
is an incidence structure  satisfying:
Lemma 1. Let (, ,  ) be a partial geometry with a
spread. Then, for any two lines  and  in the spread, there
are exactly  other lines that intersect both. Each point
on  is contained in exactly  of these lines.</p>
        </sec>
        <sec id="sec-3-1-11">
          <title>A graph  with diameter  is distance-regular if and</title>
          <p>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 distance  in ,  gives the number
of neighbors of  at distance  + 1 from , and  gives
the number of neighbors of  at distance  − 1 from .</p>
          <p>This array of integers is known as the intersection array
1. Each point is incident with  + 1 lines ( ≥ 1), of a distance-regular graph.</p>
          <p>
            and two distinct points are incident with at most As demonstrated by Brouwer in [
            <xref ref-type="bibr" rid="ref6">6</xref>
            ], removing the
one line. edges of a spread S from a strongly regular graph 
with parameters given by the point graph of (, )
2. Each line is incident with  + 1 points ( ≥ 1), results in a distance-regular graph of diameter 3 with
and two distinct lines are incident with at most an antipodal system . In this system, the relation of
one point. being at distance 3 in the distance-regular graph  − 
is an equivalence relation, with blocks corresponding to
the cliques of . Hence Lemma 2 can also be applied to
pseudo-geometric strongly regular graph with spread.
          </p>
        </sec>
        <sec id="sec-3-1-12">
          <title>The pair (, ) is called the order of  . Hereinafter,</title>
          <p>a generalized quadrangle of order (, ) is referred to as
(, ).</p>
        </sec>
        <sec id="sec-3-1-13">
          <title>Generalized quadrangles are a specific case of partial</title>
          <p>geometries. Specifically, each generalized quadrangle
of order (, ) corresponds to a partial geometry with
parameters ( + 1,  + 1, 1).</p>
        </sec>
        <sec id="sec-3-1-14">
          <title>Thus, the point graph of a generalized quadrangle of</title>
          <p>order (, ) is a strongly regular graph with parameters:
 = ( + 1)( + 1),
 = ( + 1),
 =  − 1,
 =  + 1.</p>
        </sec>
        <sec id="sec-3-1-15">
          <title>Each line in (, ) forms a clique of size 1 +  in the</title>
          <p>point graph. There are no other cliques due to the third
condition in the definition of generalized quadrangles,
which ensures that any three points inducing a 3 in the
point graph must lie on the same line.</p>
        </sec>
        <sec id="sec-3-1-16">
          <title>There is a one-to-one correspondence between spreads</title>
          <p>in (, ) and spreads in its point graph consisting of
1 +  cliques of size 1 + .</p>
        </sec>
        <sec id="sec-3-1-17">
          <title>By Lemma 1 we have that any two cliques in the spread</title>
          <p>are connected by exactly 1 +  edges, forming a perfect
matching. This is articulated as follows:
Lemma 2. If the vertices of the point graph of (, )
with a spread  are arranged according to their
corresponding cliques, the resulting adjacency matrix can be
represented by (1 + ) × (1 + ) blocks, each of size
(1 + ) × (1 + ). The diagonal blocks of the matrix
correspond to the adjacency matrices of the cliques (i.e.,
1+ − 1+), while the of-diagonal blocks are
permutation matrices, representing the incidence matrices of
1factors.</p>
          <p>Lemma 3. Let  be a pseudo-geometric or geometric
strongly regular graph with a spread  consisting of 
cliques of size . If the vertices of  are arranged according
to their corresponding cliques in , the resulting adjacency
matrix can be represented by  ×  blocks, each of size
 × . The diagonal blocks of the matrix correspond to the
adjacency matrices of the cliques (i.e.,  − ), while the
of-diagonal blocks are permutation matrices, representing
the incidence matrices of 1-factors.</p>
        </sec>
        <sec id="sec-3-1-18">
          <title>If the strongly regular graph  is geometric or pseudo</title>
          <p>geometric, the resulting distance-regular graph  −  is
termed geometric or pseudo-geometric, respectively.</p>
        </sec>
      </sec>
      <sec id="sec-3-2">
        <title>2.2. Siamese color graphs</title>
        <p>A color graph Γ is defined as a pair (, ℛ) where  is a set
of vertices and ℛ is a partition of  2, meaning that the
elements of ℛ are pairwise disjoint and ⋃︀∈ℛ  =  2.
The relations in ℛ are referred to as the colors of Γ , and
the number |ℛ| of its colors is called the rank of Γ .</p>
        <sec id="sec-3-2-1">
          <title>In other words, a color graph is any edge coloring</title>
          <p>of a complete digraph with a loop at each vertex. We
define an adjacency matrix of a color graph to be a  × 
matrix  = (, ) such that , =  if (,  ) ∈ 
for  ∈ ℛ.</p>
        </sec>
        <sec id="sec-3-2-2">
          <title>Throughout this paper, we will consider only color</title>
          <p>graphs where all their colors represent symmetric
relations, i.e., underlying graphs of non-trivial relations are
simple and undirected, and one of them is the identity
relation..</p>
        </sec>
        <sec id="sec-3-2-3">
          <title>Let Γ and Γ ′ be color graphs. An isomorphism  :</title>
          <p>Γ → Γ ′ is a bijection of  onto  ′ which induces a
bijection  : ℛ → ℛ′ of colors. A weak (or color)
automorphism of Γ is an isomorphism  : Γ → Γ . If, in
addition, the induced map  is the identity on ℛ, we call
 a (strong) automorphism of Γ .</p>
        </sec>
        <sec id="sec-3-2-4">
          <title>In 2003, Kharaghani and Torabi introduced the concept and Woldar in a series of articles [2, 3]. In these papers, of a Siamese color graph, i.e., the decomposition of a com- the authors constructed an infinite family of geometric plete graph into strongly regular graphs sharing a spread. Siamese color graphs, conjectured to be isomorphic to</title>
        </sec>
        <sec id="sec-3-2-5">
          <title>This notion is formalized in the following definition. the family of Kharaghani and Torabi, and proved the</title>
          <p>
            Geometric Siamese color graphs were studied by Re- vide a characterisation of both types of strongly regular
ichard in his thesis [
            <xref ref-type="bibr" rid="ref7">7</xref>
            ] and further by Klin, Reichard,
Definition 4.
be a color graph such that
          </p>
          <p>Let  = (, { , , 1, 2, . . . , })
1. (, ) is a partition of  into cliques of equal
size.</p>
          <p>dal system .</p>
        </sec>
        <sec id="sec-3-2-6">
          <title>2. For all , the graph (, ) is an imprimitive</title>
          <p>distance-regular graph of diameter 3 with
antipoular graph with fixed parameters.</p>
          <p>3. For all , the graph (,  ∪ ) is a strongly
reg</p>
        </sec>
        <sec id="sec-3-2-7">
          <title>Then  is a Siamese color graph. We call  the spread of</title>
          <p>Γ and  — the number of distance-regular graphs — the</p>
        </sec>
        <sec id="sec-3-2-8">
          <title>Siamese rank of  .</title>
          <p>We shall denote  by (, , , , 
) where
(, , , 
) and  is the valency of the spread . Kharaghani and</p>
        </sec>
        <sec id="sec-3-2-9">
          <title>Torabi used the term Siamese to indicate that all these</title>
          <p>) are the common parameters of all (, ∪
strongly regular graphs share a common spread.</p>
        </sec>
        <sec id="sec-3-2-10">
          <title>Moreover, Kharaghani and Torabi in [1] proved the existence of an infinite family of Siamese color graphs with special parameters.</title>
          <p>Theorem 5. For any prime power , there exists an
(1 +  + 2 + 3,  + 2,
is an SCG on 1 +  + 
2 + 3 vertices consisting of 1 + 
− 1 + , 1 + , ), which
strongly regular graphs sharing 1 + 2 disjoint cliques of
size 1 + .</p>
          <p>
            The parameters of the strongly regular graphs
mentioned above are of interest as they match those of a
point graph of a generalized quadrangle (, ).
Hereafter, Siamese color graphs with these parameters are
referred to as Siamese color graphs of order , denoted
as (). According to Brouwer’s Theorem [
            <xref ref-type="bibr" rid="ref6">6</xref>
            ], for
this class of Siamese color graphs, the verification of the
second condition in Definition 4 is unnecessary if the
remaining two conditions are met.
          </p>
          <p>A Siamese color graph () is termed geometric if
all its strongly regular graphs (,  ∪ ) are geometric,
pseudo-geometric if all its strongly regular graphs (,
 ∪ ) are pseudo-geometric, and mixed if it contains
both pseudo-geometric and geometric strongly regular
graphs (,  ∪ ).</p>
        </sec>
      </sec>
    </sec>
    <sec id="sec-4">
      <title>3. Some Known Results on</title>
    </sec>
    <sec id="sec-5">
      <title>Siamese Color Graphs</title>
      <p>following result.</p>
      <p>
        Theorem 6 ([
        <xref ref-type="bibr" rid="ref2 ref3">2, 3</xref>
        ]). Let  be a geometric Siamese color
graph of order . For each point graph (,  ∪ ),
construct the corresponding generalized quadrangle. Let 
denote the union of all lines in all resulting generalized
quadrangles. Then the incidence structure
      </p>
      <p>= (, )
is a Steiner design</p>
      <p>︂(
 =  2,  + 1,
4 − 1 )︂
 − 1
.</p>
      <sec id="sec-5-1">
        <title>Using Theorem 6, Klin, Reichard, and Woldar com</title>
        <p>
          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.
Theorem 7 ([
          <xref ref-type="bibr" rid="ref2 ref3">2, 3</xref>
          ]). Every Siamese color graph on 15
vertices is necessarily geometric. There are exactly two
non-isomorphic Siamese color graphs on 15 vertices. Their
corresponding Steiner triple systems are  (15)#1 and
 (15)#7 in the notation of [
          <xref ref-type="bibr" rid="ref8">8</xref>
          ].
        </p>
      </sec>
      <sec id="sec-5-2">
        <title>Last year we contributed to this research in [5] by</title>
        <p>completing the classification of geometric Siamese color
graphs of order 3 which can be summarised in the
following theorem.</p>
        <p>Theorem 8. There are exactly 399 non-isomorphic
Siamese color graphs on 40 vertices. Their corresponding
Steiner systems (2, 4, 40) are all non-isomorphic.
4. Siamese color graphs of order 3</p>
      </sec>
      <sec id="sec-5-3">
        <title>According to the definition, Siamese color graphs must</title>
        <p>
          have a spread consisting of ten 4 and include four
strongly regular graphs with parameters (40, 12, 2, 4).
Among the 28 strongly regular graphs of order 40 [
          <xref ref-type="bibr" rid="ref10 ref9">9, 10</xref>
          ],
only two posses a spread: one geometric — #26 in [
          <xref ref-type="bibr" rid="ref10">10</xref>
          ]
and one pseudo-geometric — #27 in [
          <xref ref-type="bibr" rid="ref10">10</xref>
          ]. The geometric
one shall be denoted  and pseudo-geometric  . For
both of these graphs, the distance-regular graphs have
intersection arrays {9, 6, 1; 1, 2, 9}. The case of a purely
geometric Siamese color graph was resolved in [
          <xref ref-type="bibr" rid="ref5">5</xref>
          ].
However, as we seek to classify both purely pseudo-geometric
        </p>
      </sec>
      <sec id="sec-5-4">
        <title>Siamese color graphs and the mixed case, we will prographs and their distance-regular graphs.</title>
        <p>4.1. Strongly regular and distance-regular
graphs with spread on 40 vertices
|(2)| = 144). Let us note that elements of our table
comply with the following lemma:
The geometric strongly regular graph  is the point Lemma 9. Let , denote the number of graphs in
graph of (3, 3). It contains 40 cliques of size 4. It pos- Γ (), which are edge-disjoint with Γ . Then , ·
sesses 36 diferent spreads, all of which can be mapped |(Γ  )| = , · | (Γ )|.
onto each other under the group of automorphisms. Its
group of automorphisms comprises 51 840 elements, Furthermore, we observed that some instances of
with the stabilizer of the spread having 1 440 elements. distance-regular graphs form twins with the three
aforeHowever, there is only one non-trivial automorphism mentioned distance-regular graphs in a significantly
betthat also fixes the order of cliques in the spread. Distance- ter way than others. Specifically, they produce a much
regular graph of  will be denoted 1. greater number of Siamese color graphs that contain</p>
        <p>The pseudo-geometric strongly regular graph  con- them compared to the relatively small number of graphs
tains only 22 cliques of size 4, with only four possible that do not contain any such distance regular graphs. A
spreads. One of these is stable under the group of auto- notion of preferred twin is introduced to describe this
morphisms while other three map onto each other. Its surprising phenomenon in our results. A twin Γ ′ of Γ is
group of automorphisms comprises 432 elements. We defined as a preferred twin if there exists a further
divianalyse this scenario in two distinct cases, especially sion of vertices in the cliques of the spread into pairs such
since removing all edges of one of these spreads from that the mapping  : () → (), which exchanges
the graph always results in one of two non-isomorphic vertices in these pairs, is a fixed-point-free involution and
distance-regular graphs. an automorphism on . The preferred twin ′ is a graph</p>
        <p>In case of one stable spread, the stabilizer of the spread on the same set of vertices as , with edges such that
is identical to the group of automorphisms and there are (, ) ∈ () ⇔ (,  ()) ∈ (′). This mapping 
three non-trivial automorphisms that also fix the order shall be called a preferred pairing.
of cliques in the spread. The distance-regular graph of  It can be shown that ′ is a strongly regular graph with
is then denoted 1. the same set of parameters as . All the preferred twins</p>
        <p>In case of three isomorphic spreads, the stabilizer of found in our computations consist of two isomorphic
the spread has 144 elements, and the only automorphism distance-regular graphs .
that fixes the order of cliques in spread is trivial e.g. the The graph 1 has a unique preferred twin. Its
autoidentity. The distance-regular graph of  is then denoted morphism group is identical to (1). There are three
2. preferred twins for 1, forming one orbit under the
action of (1) ∩ (). All the referred twins of 1
are also preferred twins pair-wise. There is no preferred
4.2. (Siamese) twins and preferred twins twin for 2.</p>
        <p>In what follows  will always be the spread on Remark 10. Let  and ′ be preferred twins,  be their
40 vertices with cliques {1, 2, 3, 4}, {5, 6, 7, 8}, . . . , preferred pairing, and  and  ′ be their adjacency
{37, 38, 39, 40} and any distance regular graph will matrices, respectively. Then  ′ can be derived from 
have parameters {9, 6, 1; 1, 2, 9} and antipodal system . by applying  only to the rows or only to the columns
Graphs 1, 1, 2 mentioned above will be lexicograph- of  . Hence, if the rows and columns within cliques are
ically maximal elements of their orbits (1), (1) arranged so that rows exchanged by  are adjacent, this
and (2) of (), respectively. further subdivides the blocks of size 4 × 4 in both  and</p>
        <p>We say that two distance regular graphs  and ′ are  ′ into 2 × 2 blocks in such a way that each of them
twins if they are edge-disjoint. is either all-zero, 2, or 2 − 2. Moreover,  and  ′</p>
        <p>During our computations we found all twins , ′ have all all-zero blocks in the same positions, and  has
such that  is one of the above mentioned graphs its 2 blocks in the positions where  ′ has 2 − 2, and
1, 1, 2 and ′ is isomorphic to one of them. Num- vice versa. This phenomenon is further illustrated by the
bers of possible twins are summarised in the following following minor of the matrix 1 + 2 × ′1.
table.</p>
        <p>∖′
1
1
2</p>
        <p>1
Graphs are ordered by the size of their
automorphism group (|(1)| = 1440, |(1)| = 432,
. . . , {37, . . . , 40}. This choice of  facilitated
representation of graphs during computations by:</p>
      </sec>
      <sec id="sec-5-5">
        <title>1We also ran it for the geometric case and thus have an independent</title>
        <p>
          verification of the results from [
          <xref ref-type="bibr" rid="ref5">5</xref>
          ]. This computation previously
        </p>
        <p>To further accelerate the computation, the fact that
 = (Γ 1) ≤ () was exploited.
Specifically, only permutations  from a transversal of 10 =
• adjacency matrix – 40 × 40 matrices that can ()/410 with respect to /410 were tested, and for
be divided into 10 × 10 blocks of size 4 × 4. From a given , only  from diferent cosets of  in 410 were
the Lemma 3, of-diagonal blocks are permutation considered.
matrices. The distance-regular graphs have zero Step 3:
matrices in place of diagonal blocks – Step 1, 3 Graphs in the set  are sorted into sets by the second to
• binary number representation – numbers iffth block (of size 4 × 4) in the first row of its adjacency
such that the binary AND of any two returns zero matrix. We shall refer to these blocks as 2, 3, 4, and
if and only if the distance-regular graphs they rep- 5. The first block is zero, since Γ  is a distance-regular
resent are edge-disjoint. These are generated by graph. In Γ 1 we have 2 = 3 = 4 = 5 = 4.
concatenating rows of each block matrix above Firstly the graphs in the set  are sorted into three sets
the diagonal into one 16 digit binary number, and denoted 2, 3, and 4, based on the position of 1 in the
then concatenating these – Steps 2 and 3. ifrst row of 2 in their adjacency matrices. Since Γ 1 has
1 at position (1, 1), adjacency matrices of each graph in
• permutation matrix representation – matri-  must have 1 at exactly one of the positions (1, ),  ∈
ces 10 × 10 such that every entry represents a {2, 3, 4}. The division of  into 2, 3, and 4 follows
4 × 4 block in their adjacency matrices. Since naturally. It is easy to see, that for any triples Γ 2, Γ 3, Γ 4
these blocks are either permutation matrices of mutually edge-disjoint distance-regular graphs in ,
or all-zero, they can be represented by num- no two Γ , Γ  belong to the same . Therefore, without
bers in {0, 1, . . . , 24}. Specifically, all-zero is the loss of generality we can assume that Γ  ∈  for
represented by 0, and permutation matrices by  = 2, 3, 4.
{1, . . . , 24} in such a way that the greater the 16 This is further subdivided into subsets by the blocks
digit number derived by concatenation of rows 2, 3, 4, and 5. There are only 4 combinations
of a block, the smaller the entry in matrix repre- of three permutation matrices (of size 4 × 4) such that
sentation, e.g.,  is represented by 1 – Steps 1, 2, the sum of these matrices and an identity matrix yields
and 4. an all-ones matrix. A list of all possible combinations
of permutation matrices in the blocks 2, 3, 4, and
5 for Γ ,  = 2, 3, 4 was made and the computations
were distributed in such a way that in each instance we
restricted candidates for Γ 2 and Γ 3 to graphs with the
prescribed second to fifth block of the first row of the
adjacency matrix.</p>
      </sec>
      <sec id="sec-5-6">
        <title>Previously, when this step was executed for purely geo</title>
        <p>metric Siamese color graphs, possible edge-disjoint pairs
of Γ 2 and Γ 3 were checked by examining all
combinations from two lists. This check involved simply applying
AND to all possible pairs, as this returns 0 exactly when
graphs are edge-disjoint. While this method suficed for
the purely geometric case, the purely pseudo-geometric
case involved 30 times more possible Γ 2, Γ 3, and Γ 4
matrices. Consequently, comparing two lists would take on
average 900 times longer, and this part of computation
would take almost a month.</p>
      </sec>
      <sec id="sec-5-7">
        <title>However, improvements were made by storing binary</title>
        <p>representations of possible Γ 2s in a prefix tree data
structure. This class included a method that, given as an input
a binary representation of Γ 3, yielded binary
representations of all Γ 2 that were edge-disjoint to the given Γ 3.</p>
      </sec>
      <sec id="sec-5-8">
        <title>This enhancement significantly accelerated our program,</title>
        <p>reducing the computation time to less than an hour1.
The binary number representation allows us to compare
individual graphs and to introduce an ordering both on 
a set of all Siamese color graphs. Hereinafter the ordering
of distance-regular graphs in  is given by the ordering
of their binary representations. Siamese color graphs are
represented by quadruple of their distance-regular graphs
in descending order and ordered by this representation
as well.</p>
      </sec>
      <sec id="sec-5-9">
        <title>To avoid the repetitions of the Siamese color graphs in Step 3 we are striving to find only the greatest representation for each Siamese color graph.</title>
        <p>Step 1:
As we are looking for greatest representation for each of
the Siamese color graphs, Γ 1 was chosen as the graph
with the greatest binary number representation.
Consequently, all blocks beside the first one in the first row of
the adjacency matrix of Γ 1 are , and all entries except
the first one of the permutation matrix representation
are 1.</p>
        <p>Step 2:</p>
      </sec>
      <sec id="sec-5-10">
        <title>In order to obtain all images of Γ 1 in () the action</title>
        <p>of () = 4 ≀ 10 = 410 ⋊ 10 on the cliques of
 was utilized in the following way. For each  in 10,
an auxiliary graph Γ ′ = Γ 1 was constructed, and then a
backtrack procedure was used to filter all  ∈ 410 such
that Γ ′ is edge-disjoint with Γ 1.</p>
        <p>Clearly, in each Siamese color graph of order 3, Γ 4 isomorphic distance-regular graphs in a mixed Siamese
is uniquely determined by , Γ 1, Γ 2, and Γ 3. It was color graph.
found that for given edge-disjoint Γ 2 and Γ 3, it was It is straightforward to count that there are 6
possifaster to first check whether 40 − (Γ 1 ∪ Γ 2 ∪ Γ 3) ble combinations of distance-regular graphs: 3
combiwas a (40, 12, 2, 4), and only then verify whether nations with two isomorphic pairs and 3 combinations
it belongs to set . Instances of Γ 4 such that Γ 4 +  with one isomorphic pair and one of each remaining
is (40, 12, 2, 4) but Γ 4 is not in , would be also re- distance-regular graphs. The remaining task is to assign
tained, as they would be useful in constructions of the the order in which these are assigned to Γ 1, Γ 2, Γ 3, and
mixed Siamese color graphs, however these instances did Γ 4. Clearly, for any mixed Siamese color graph and any
not occur. distance-regular graph  it contains, there exists an
iso</p>
        <p>Interestingly, both in the case of Siamese graphs con- morphic mixed Siamese color graph with Γ 1 isomorphic
sisting of four 1 and of four 1, one preferred twin of to . In other words, for any combination, we can choose
Γ 1 belongs to Γ 2 and it has the largest binary represen- which distance-regular graph is going to be Γ 1.
Furthertation in the whole . Since we are looking for greatest more, the stabilizer of 1 as Γ 1 in () permutes the
representation for each of the Siamese color graphs, we block 2 in adjacency matrix in such a way that we can
can divide our search into two cases. First being the case arbitrarily choose the order in which the other three
without the preferred twins, here we discard all the pre- distance-regular graphs are assigned to Γ 2, Γ 3, and Γ 4
ferred twins of Γ 1 out of  and the rest is the same. In without loss of generality. This flexibility allows us to
the later case, we start with preferred twins as Γ 1, Γ 2 solve all five cases containing 1 without further case
and we can discard most of the possible Γ 3 in such a way, work. The only remaining case consists of two 2s and
that we only check for those Γ 3, that have the largest two 1s. There, the stabilizer of 2 as Γ 1 in ()
perbinary representation in their orbit under the weak au- mutes the first permutation block of adjacency matrices
tomorphism group of color graph with colors , Γ 1 and in such a way that we can choose which distance-regular
Γ 2. graph will be Γ 2, and hence we can choose both Γ 1 and</p>
        <p>Step 4: Γ 2 to be isomorphic to 2, and so both Γ 3 and Γ 4 must</p>
      </sec>
      <sec id="sec-5-11">
        <title>Instead of testing all obtained Siamese color graphs be isomorphic to 1.</title>
        <p>for isomorphisms, it sufices to check whether their bi- Further diferences lie in Steps 2 and 3, afecting the
nary representation is maximal in the action of (). set  and its subsequent subdivision. In Step 2, the
repreGraph Γ 1 already has a lexicographically maximal bi- sentatives of the cosets of  in () are not applied
nary representation in its orbit under the action of to Γ 1, but rather to those of 1, 1, and 2 that were
(). Therefore, for any Siamese color graph  = previously assigned to Γ 2, Γ 3, or Γ 4, yielding one set 
(, { , , Γ 1, Γ 2, Γ 3, Γ 4}), it is suficient to select one for each of the considered 1, 1, and 2. These sets
map   such that  (Γ ) = Γ 1 for all  ∈ {1, 2, 3, 4}, are then further divided or filtered in Step 3 in an
eviand then check all maps of the form   where  ∈ dent manner. In Step 4,   is only selected for those  for
(Γ 1). which Γ  is isomorphic to Γ 1.</p>
      </sec>
      <sec id="sec-5-12">
        <title>Our strategy was implemented using Python [11], GAP</title>
        <p>
          [
          <xref ref-type="bibr" rid="ref12">12</xref>
          ], and GAP packages GRAPE and DESIGN [
          <xref ref-type="bibr" rid="ref13 ref14">13, 14</xref>
          ].
        </p>
        <sec id="sec-5-12-1">
          <title>5.2. Mixed case</title>
          <p>The search for mixed Siamese color graphs is very
similar to the pure cases. We have to consider how many 6. Results
geometric and how many and which pseudo-geometric
distance-regular graphs are to be in the final Siamese Let us begin with some preliminary results which may
color graph and in what order are they to be assigned to be of independent interest. In the Step 3, for Γ 1
isomorΓ 1, Γ 2, Γ 3, and Γ 4. This was facilitated by including a phic to 2 there were no two graphs Γ 2 and Γ 3 with no
simple step in the previous cases. In Step 3, we always common edges.
ifrst checked if Γ 4 +  was strongly regular, and only af- Lemma 15. No Siamese color graphs contains 2 as a
terward verified whether it belonged to set . As a result distance-regular factors.
of these computations we have that there are no mixed
Siamese color graphs containing three isomorphic copies Moreover, in the Step 3 for Γ 1, Γ 2 and Γ 3 being either
of a distance regular graph. Hence, a mixed Siamese reg- all isomorphic to 1 or all isomorphic to 1, all possible
ular graph contains at most two pairs. However, by the Γ 4 were isomorphic to Γ 1 as well. Hence, if there is
pigeonhole principle, there must be at least one pair of a Siamese color graph with three isomorphic distance
regular graphs then the fourth is isomorphic to the others
as well.
took about a day but now was finished in the matter of minutes.</p>
          <p>Theorem 16. Siamese color graphs of order 3 exist in
three forms:
• geometric; all distance-regular factors are
isomor</p>
          <p>phic to 1,
• pseudo-geometric; all distance-regular factors are</p>
          <p>isomorphic to 1
• mixed; two distance-regular factors are isomorphic</p>
          <p>to 1 the rest is isomorphic to 1.</p>
        </sec>
      </sec>
      <sec id="sec-5-13">
        <title>For the sake of completenesses we state the improved</title>
      </sec>
      <sec id="sec-5-14">
        <title>Theorem 8.</title>
        <p>Theorem 8*. There are exactly 399 non-isomorphic
Siamese color graphs on 40 vertices, 357 of them consist of
two preferred twins. Their corresponding Steiner systems
(2, 4, 40) are all non-isomorphic.</p>
        <p>Theorem 17. There are 20 354 pseudo-geometric Siamese
color graphs, 20 030 of them consist of two preferred twins
— in one instance any two of its distance-regular factors are
preferred twins. Remaining 324 pseudo-geometric Siamese
color graphs contain no preferred twins.</p>
        <p>Theorem 18. There is 4 492 mixed Siamese color graphs,
4 480 of them consist of two preferred twins: one set of
twins is geometric and the other is pseudo-geometric. The
remaining 12 Siamese color graphs contain no preferred
twins.</p>
      </sec>
      <sec id="sec-5-15">
        <title>For each of the 20 354 pseudo-geometric and 4 492</title>
        <p>mixed Siamese color graphs of order 3, some algebraic
properties were computed. These properties pertain to
the given Siamese color graphs and a block design derived
from them in a manner similar to Theorem 6. In the tables
below, each row represents a group of non-isomorphic
Siamese color graphs that otherwise share all computed
properties. The computed properties for Siamese color
graphs include the automorphism group (column marked
as A(SCG)), its orbit on vertices (O(SCG)), and the weak
automorphism group (WA(SCG)). For the block design
derived from cliques of the Siamese color graph, the
automorphism group (A(BD)) and its orbits on the blocks
(O(BD)) were computed. To simplify the table, only the
sizes of the identified groups and orbits are stated. The
last column indicates how many of these non-isomorphic</p>
      </sec>
      <sec id="sec-5-16">
        <title>Siamese color graphs contain at least one preferred twin.</title>
      </sec>
    </sec>
    <sec id="sec-6">
      <title>7. Acknowledgment</title>
      <sec id="sec-6-1">
        <title>The authors acknowledge support from the APVV Research Grant APVV-19-0308 and from the VEGA Research Grants 1/0423/20, 1/0727/22 and 1/0437/23.</title>
        <p>|A(SCG)|
72
72
72
72
72
36
36
36
36
36
24
24
12
12
12
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
6
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4</p>
        <p>Table 1: Pseudo-geometric Siamese color graphs for  = 3.
O(SCG) |A(BD)| O(BD) WA(SCG) # preferred / #
4, 36 1728 1, 9, 48 1728 1/1
4, 36 1728 1, 9, 48 864 0/1
4, 36 1728 1, 9, 48 576 1/1
4, 36 1728 1, 9, 48 288 1/1
4, 36 1728 1, 9, 48 144 0/1
22, 182 576 1, 9, 48 288 2/2
22, 182 576 1, 9, 48 144 0/1
22, 182 576 1, 9, 48 144 0/1
22, 182 576 1, 9, 48 144 0/1
22, 182 576 1, 9, 48 72 0/1
4, 12, 24 72 1, 3, 4, 6, 8, 36 72 0/2
4, 12, 24 48 1, 3, 4, 6, 8, 12, 24 48 4/4
22, 62, 122 48 1, 3, 4, 6, 8, 12, 24 24 2/2
22, 62, 122 24 1, 22, 3, 42, 63, 122 24 8/8
4, 123 24 1, 3, 43, 6, 12, 24 24 4/4
42, 84 1728 1, 9, 48 192 0/1
42, 84 1728 1, 9, 48 96 0/1
42, 84 1728 1, 9, 48 64 0/1
42, 84 96 12, 8, 16, 32 96 0/4
42, 84 64 12, 8, 16, 32 64 2/4
42, 84 64 12, 8, 16, 32 32 1/1
42, 84 64 2, 8, 16, 32 64 4/8
42, 84 64 2, 8, 16, 32 32 2/2
42, 84 32 12, 42, 82, 162 32 8/12
42, 84 32 2, 8, 16, 32 32 0/2
42, 84 32 12, 8, 16, 32 32 0/2
42, 84 32 2, 8, 16, 32 32 0/12
42, 84 24 12, 2, 4, 6, 8, 12, 24 24 0/4
42, 84 16 12, 22, 43, 83, 16 16 12/20
42, 84 16 2, 42, 82, 162 16 2/24
42, 84 16 2, 42, 82, 162 8 1/1
42, 84 16 12, 42, 82, 162 16 2/25
42, 84 16 12, 42, 82, 162 8 1/1
42, 84 8 12, 24, 44, 84 8 0/44
22, 66 24 1, 3, 43, 6, 12, 24 12 2/2
24, 48 576 1, 9, 48 32 0/1
24, 48 576 1, 9, 48 16 0/1
24, 48 64 12, 8, 16, 32 32 2/3
24, 48 64 2, 8, 16, 32 16 2/2
24, 48 32 12, 83, 162 32 8/10
24, 48 32 12, 83, 162 16 4/5
24, 48 32 12, 83, 162 16 0/2
24, 48 32 12, 42, 82, 162 16 4/5
24, 48 16 12, 83, 162 16 2/4
24, 48 16 12, 83, 162 8 1/1
24, 48 16 12, 22, 43, 83, 16 8 6/8
24, 48 16 12, 44, 83, 16 8 8/8
24, 48 16 12, 46, 84 16 40/46
24, 48 16 12, 83, 162 8 0/1
24, 48 16 2, 42, 82, 162 4 1/1
24, 48 16 2, 83, 162 16 2/2
24, 48 16 2, 83, 162 8 1/1
24, 48 16 2, 83, 162 4 1/1
24, 48 16 12, 83, 162 16 0/1
24, 48 16 12, 42, 82, 162 8 2/3
24, 48 16 12, 83, 162 16 0/1
24, 48 16 12, 83, 162 8 2/2
24, 48 16 12, 44, 83, 16 16 16/16
24, 48 16 12, 83, 162 8 0/1
24, 48 8 12, 26, 47, 82 8 152/162
24, 48 8 12, 22, 45, 84 4 4/4</p>
      </sec>
      <sec id="sec-6-2">
        <title>The table continues on the next page.</title>
      </sec>
    </sec>
  </body>
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          [1]
          <string-name>
            <given-names>H.</given-names>
            <surname>Kharabani</surname>
          </string-name>
          ,
          <string-name>
            <given-names>R.</given-names>
            <surname>Torabi</surname>
          </string-name>
          ,
          <article-title>On a decomposition of complete graphs</article-title>
          ,
          <source>Graphs &amp; Combinatorics</source>
          <volume>19</volume>
          (
          <year>2003</year>
          )
          <fpage>519</fpage>
          -
          <lpage>526</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          [2]
          <string-name>
            <given-names>M.</given-names>
            <surname>Klin</surname>
          </string-name>
          ,
          <string-name>
            <given-names>S.</given-names>
            <surname>Reichard</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Woldar</surname>
          </string-name>
          ,
          <article-title>Siamese objects, and their relation to color graphs, association schemes and steiner designs</article-title>
          ,
          <source>Bulletin of the Belgian Mathematical Society - Simon Stevin</source>
          <volume>12</volume>
          (
          <year>2005</year>
          )
          <fpage>845</fpage>
          -
          <lpage>857</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          [3]
          <string-name>
            <given-names>M.</given-names>
            <surname>Klin</surname>
          </string-name>
          ,
          <string-name>
            <given-names>S.</given-names>
            <surname>Reichard</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Woldar</surname>
          </string-name>
          ,
          <article-title>Siamese combinatorial objects via computer algebra experimentation, Algorithmic algebraic combinatorics and Gröbner bases (</article-title>
          <year>2009</year>
          )
          <fpage>67</fpage>
          -
          <lpage>112</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation>
          [4]
          <string-name>
            <given-names>P. B.</given-names>
            <surname>Gibbons</surname>
          </string-name>
          ,
          <string-name>
            <given-names>R.</given-names>
            <surname>Mathon</surname>
          </string-name>
          ,
          <article-title>Construction methods for bhaskar rao and related designs</article-title>
          ,
          <source>Journal of the Australian Mathematical Society</source>
          <volume>42</volume>
          (
          <year>1987</year>
          )
          <fpage>5</fpage>
          -
          <lpage>30</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation>
          [5]
          <string-name>
            <given-names>N.</given-names>
            <surname>Hronkovičová</surname>
          </string-name>
          ,
          <string-name>
            <given-names>M.</given-names>
            <surname>Mačaj</surname>
          </string-name>
          ,
          <article-title>On geometric siamese color graphs (</article-title>
          <year>2023</year>
          ).
        </mixed-citation>
      </ref>
      <ref id="ref6">
        <mixed-citation>
          [6]
          <string-name>
            <given-names>A. E.</given-names>
            <surname>Brouwer</surname>
          </string-name>
          ,
          <article-title>Distance regular graphs of diameter 3 and strongly regular graphs</article-title>
          ,
          <source>Discrete mathematics 49</source>
          (
          <year>1984</year>
          )
          <fpage>101</fpage>
          -
          <lpage>103</lpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref7">
        <mixed-citation>
          [7]
          <string-name>
            <given-names>S.</given-names>
            <surname>Reichard</surname>
          </string-name>
          ,
          <article-title>Computational and theoretical analysis of coherent configurations and related incidence structures</article-title>
          ,
          <year>2003</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref8">
        <mixed-citation>
          [8]
          <string-name>
            <given-names>R.</given-names>
            <surname>Mathon</surname>
          </string-name>
          ,
          <string-name>
            <given-names>K. T.</given-names>
            <surname>Phelps</surname>
          </string-name>
          ,
          <string-name>
            <given-names>A.</given-names>
            <surname>Rosa</surname>
          </string-name>
          ,
          <article-title>Small Steiner triple systems and their properties</article-title>
          , MacMaster University. Department of Mathematical Sciences,
          <year>1982</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref9">
        <mixed-citation>
          [9]
          <string-name>
            <given-names>E.</given-names>
            <surname>Spence</surname>
          </string-name>
          , The strongly regular (
          <volume>40</volume>
          ,
          <issue>12</issue>
          ,
          <issue>2</issue>
          , 4) graphs,
          <source>The Electronic Journal of Combinatorics</source>
          <volume>7</volume>
          (
          <year>2000</year>
          ) #
          <fpage>R22</fpage>
          .
        </mixed-citation>
      </ref>
      <ref id="ref10">
        <mixed-citation>
          [10]
          <string-name>
            <given-names>E.</given-names>
            <surname>Spence</surname>
          </string-name>
          ,
          <source>Strongly regular graphs on at most 64 vertices/srg(40</source>
          ,
          <issue>12</issue>
          ,
          <issue>2</issue>
          ,
          <issue>4</issue>
          ), http://www.maths.gla.ac.uk/ es/SRGs/40-12- 2-4, ????
        </mixed-citation>
      </ref>
      <ref id="ref11">
        <mixed-citation>
          [11]
          <string-name>
            <given-names>G.</given-names>
            <surname>Van Rossum</surname>
          </string-name>
          ,
          <string-name>
            <given-names>F. L.</given-names>
            <surname>Drake</surname>
          </string-name>
          , Python 3 Reference Manual, CreateSpace, Scotts Valley, CA,
          <year>2009</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref12">
        <mixed-citation>
          [12]
          <string-name>
            <surname>GAP - Groups</surname>
          </string-name>
          , Algorithms, and Programming,
          <source>Version</source>
          <volume>4</volume>
          .11.0, https://www.gap-system.
          <source>org</source>
          ,
          <year>2020</year>
          .
        </mixed-citation>
      </ref>
      <ref id="ref13">
        <mixed-citation>
          [13]
          <string-name>
            <given-names>L. H.</given-names>
            <surname>Soicher</surname>
          </string-name>
          ,
          <source>The GRAPE package for GAP, Version 4.8</source>
          .3, https://gap-packages.github.io/ grape,
          <year>2019</year>
          . Refereed GAP package.
        </mixed-citation>
      </ref>
      <ref id="ref14">
        <mixed-citation>
          [14]
          <string-name>
            <given-names>L. H.</given-names>
            <surname>Soicher</surname>
          </string-name>
          ,
          <source>The DESIGN package for GAP, Version</source>
          <volume>1</volume>
          .7, https://gap-packages.github.io/ design,
          <year>2019</year>
          . Refereed GAP package.
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>