ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.29560 J. Algebra Comb. Discrete Appl. 3(3) • 145–154 Received: 19 September 2015 Accepted: 06 December 2015 Journal of Algebra Combinatorics Discrete Structures and Applications Enumeration of symmetric (45,12,3) designs with nontrivial automorphisms∗ Research Article Dean Crnković, Doris Dumičić Danilović, Sanja Rukavina Abstract: We show that there are exactly 4285 symmetric (45,12,3) designs that admit nontrivial automor- phisms. Among them there are 1161 self-dual designs and 1562 pairs of mutually dual designs. We describe the full automorphism groups of these designs and analyze their ternary codes. R. Mathon and E. Spence have constructed 1136 symmetric (45,12,3) designs with trivial automorphism group, which means that there are at least 5421 symmetric (45,12,3) designs. Further, we discuss trigeodetic graphs obtained from the symmetric (45, 12, 3) designs. We prove that k-geodetic graphs constructed from mutually non-isomorphic designs are mutually non-isomorphic, hence there are at least 5421 mutually non-isomorphic trigeodetic graphs obtained from symmetric (45, 12, 3) designs. 2010 MSC: 05B05, 20D45, 94B05, 05C38 Keywords: Symmetric design, Linear code, Automorphism group, k-geodetic graph 1. Introduction The terminology and notation in this paper for designs and codes are as in [2, 3, 6]. One of the main problems in design theory is that of classifying structures with given parameters. Classification of designs has been considered in detail in the monograph [17]. Complete classification of designs with certain parameters has been done just for some designs with relatively small number of points, and in the case of symmetric designs complete classification is done just for a few parameter triples (see [22]). The classification of projective planes of order 9 has been solved in 1991 (see [20]), and Kaski and Östergård classified all biplanes with k=11 in 2008 (see [18]). Hence, the parameter triple (45,12,3) is the next for symmetric designs of order 9 to be classified. Since the complete classification of symmetric (45,12,3) designs seems to be out of reach with the current techniques and computers, only ∗ This work has been fully supported by Croatian Science Foundation under the project 1637. Dean Crnković (Corresponding Author), Doris Dumičić Danilović, Sanja Rukavina; Department of Mathe- matics, University of Rijeka, Radmile Matejčić 2, 51000 Rijeka, Croatia (email: deanc@math.uniri.hr, ddu- micic@math.uniri.hr, sanjar@math.uniri.hr). 145 D. Crnković et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 145–154 partial classification of such designs, with certain constrains, is possible. In this paper we manage to classify all symmetric (45,12,3) designs with nontrivial automorphisms. The first symmetric (45,12,3) design was constructed in [1], and further two symmetric (45,12,3) designs were constructed in [23] as (45,12,3) difference sets. Later on, Kölmel [19] and Ćepulić [5] have independently constructed symmetric (45,12,3) designs having an automorphism of order 5. In his doctoral dissertation [19] Kölmel also determined all (45,12,3) designs having a fixed-point-free auto- morphism of order 3. Finally, Mathon and Spence [25] showed that there are at least 3752 symmetric (45,12,3) designs, 1136 of them having a trivial automorphism group. Furthermore, Coolsaet, De Jager and Spence, established in [7] that there are exactly 78 non-isomorphic strongly regular graphs with parameters (45,12,3,3), meaning that there are exactly 78 symmetric designs having symmetric incidence matrix with zero diagonal. Ternary codes spanned by the adjacency matrices of these strongly regular graphs (i.e. incidence matrices of the corresponding symmetric designs) have been studied in [8]. The symmetric (45,12,3) design admitting a primitive action of the group PSp(4, 3) is described in [10] and [12]. In this paper we give the classification of all symmetric (45,12,3) designs having a nontrivial automor- phism group. We show that there exist exactly 4285 symmetric (45,12,3) designs that admit nontrivial automorphisms, which means that there are at least 5421 symmetric (45,12,3) designs. Furthermore, we discuss trigeodetic graphs obtained from the symmetric (45, 12, 3) designs and prove that mutually non-isomorphic designs produce mutualy non-isomorphic k-geodetic graphs. The paper is organized as follows: after the brief introduction, in Section 2 we give basic information concerning the construction method, in Section 3 we describe the construction of symmetric (45,12,3) designs with nontrivial automorphisms and give a list of the designs and their full automorphism groups, Section 4 gives information about the codes of the constructed designs, and in Section 5 we discuss trigeodetic graphs obtained from the symmetric (45, 12, 3) designs. For the construction of designs we have used our own computer programs. For isomorphism testing, and to obtain and analyze the full automorphism groups of the designs we have used [14] and [30]. The codes have been analyzed using Magma [4]. 2. Outline of the construction An incidence structure D = (P,B,I), with point set P, block set B and incidence I is a t-(v,k,λ) design, if |P| = v, every block B ∈ B is incident with precisely k points, and every t distinct points are together incident with precisely λ blocks. A design is called symmetric if it has the same number of points and blocks. An automorphism of a design D is a permutation on P which sends blocks to blocks. The set of all automorphisms of D forms its full automorphism group denoted by Aut(D). Let D = (P,B,I) be a symmetric (v,k,λ) design and G ≤ Aut(D). The group action of G produces the same number of point and block orbits (see [21, Theorem 3.3]). We denote that number by t, the point orbits by P1, . . . ,Pt, the block orbits by B1, . . . ,Bt, and put |Pr| = ωr and |Bi| = Ωi. An automorphism group G is said to be semi-standard if, after possibly renumbering orbits, we have ωi = Ωi, for i = 1, . . . , t. We denote by γir the number of points of Pr which are incident with a representative of the block orbit Bi. For these numbers the following equalities hold (see [5, 9, 16]): t∑ r=1 γir = k , (1) t∑ r=1 Ωj ωr γirγjr = λΩj + δij · (k −λ) . (2) Definition 2.1. A (t × t)-matrix (γir) with entries satisfying conditions (1) and (2) is called an orbit matrix for the parameters (v,k,λ) and orbit lengths distributions (ω1, . . . ,ωt), (Ω1, . . . , Ωt). 146 D. Crnković et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 145–154 The construction of designs admitting an action of a presumed automorphism group, using orbit matrices, consists of the following two basic steps (see [5, 9, 16]): 1. Construction of orbit matrices for the given automorphism group, 2. Construction of block designs for the orbit matrices obtained in this way. This step is often called an indexing of orbit matrices. In order to construct the orbit matrices for an action of a presumed automorphism group we have to determine all possibilities for the orbit lengths distributions. The following facts, that one can use in that purpose, can be found in [21]. Theorem 2.2. An automorphism ρ of a symmetric design fixes an equal number of points and blocks. Moreover, ρ has the same cyclic structure, whether considered as a permutation on points or on blocks. Theorem 2.3. Suppose that a nonidentity automorphism ρ of a nontrivial symmetric (v,k,λ) design fixes f points. Then f ≤ v − 2n and f ≤ λ k − √ n v, where n = k −λ is the order of the design. Moreover, if equality holds in either inequality, ρ must be an involution and every non-fixed block contains exactly λ fixed points. Theorem 2.4. Suppose that D is a nontrivial symmetric (v,k,λ) design, with an involution ρ fixing f points and blocks. If f 6= 0, then f ≥ { 1 + k λ , if k and λ are both even, 1 + k−1 λ , otherwise. Suppose that D is a symmetric (v,k,λ) design with an automorphism ρ of prime order p fixing f points. Then f ≡ v (mod p), and 〈ρ〉 acts semi-standardly on D. In that case, since the action of G = 〈ρ〉 is semi-standard, it is sufficient to determine point orbit lengths distribution (ω1, . . . ,ωt). After determining the orbit lengths distributions we proceed with the construction of orbit matrices and corresponding designs, as described in [9]. 3. Classification of symmetric (45,12,3) designs with nontrivial automorphisms In this section we give the classification of all symmetric (45,12,3) designs that admit nontrivial automorphisms. It is known that if ρ is a nonidentity automorphism of a symmetric (45,12,3) design, then |ρ| ∈ {2, 3, 5, 11} (see [25]). It has been shown in [5, 19, 25] that there are exactly 13 symmetric (45,12,3) designs with an automorphism of order 5, and exactly one symmetric (45,12,3) design with an automorphism of order 11. To complete the classification of symmetric (45,12,3) designs with nontrivial automorphisms, we have to classify all symmetric (45,12,3) designs that admit an automorphism of order 2 or 3. 3.1. Symmetric (45,12,3) designs admitting Z2 as an automorphism group Let ρ be an involutory automorphism of a symmetric (45, 12, 3) design fixing f points. Then 5 ≤ f ≤ 15 and f ≡ 1 (mod 2), hence f ∈ {5, 7, 9, 11, 13, 15}. Up to isomorphism there are 682 orbit structures, that produce 2987 mutually non-isomorphic designs. Information about the number of the orbit structures and the designs are given in Table 1. 147 D. Crnković et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 145–154 Table 1. Symmetric (45,12,3) designs having Z2 as an automorphism group number of fixed points 5 7 9 11 13 15 number of orbit structures 233 397 32 4 11 5 number of orbit structures that produce designs 45 271 30 0 7 5 number of designs 603 1898 524 0 225 28 3.2. Symmetric (45,12,3) designs admitting Z3 as an automorphism group It was determined in [8] that there are exactly 591 orbit matrices for the group Z3 acting on symmetric (45,12,3) designs. From these orbit matrices we have obtained up to isomorphism exactly 2108 symmetric (45,12,3) designs that admit an automorphism of order three. Information about the number of the orbit matrices and the constructed designs are presented in Table 2. Table 2. Symmetric (45,12,3) designs having Z3 as an automorphism group number of fixed points 0 3 6 9 number of orbit structures 293 245 49 4 number of orbit structures that produce designs 19 25 24 4 number of designs 244 482 125 1775 3.3. All symmetric (45,12,3) designs admitting a nontrivial automorphism group Comparing the designs described in subsections 3.1 and 3.2 we conclude that up to isomorphism there are exactly 4280 symmetric (45,12,3) designs that admit an automorphism of order 2 or 3. It is known from [5, 19, 25] that there are exactly 13 symmetric (45,12,3) designs with an automorphism of order 5, and only four of them have the full automorphism group whose order is not divisible by 2 or 3. Further, there is exactly one symmetric (45,12,3) design with an automorphism of order 11, and the full automorphism group of that designs is Z11. That shows that there exist exactly 4285 symmetric (45,12,3) designs with a nontrivial automorphism group. Among them there are 1161 self-dual designs and 1562 pairs of mutually dual designs. Information about these 4285 designs and their full automorphism groups are given in Table 3. Some od the automorphism groups have the same description of the structure, but they are not isomorphic. In that case, nonisomorphic groups with the same structure are listed in separate rows of Table 3 (e.g. two groups of order 324 having the structure (E27 : Z3) : E4). Since Mathon and Spence have constructed 1136 symmetric (45,12,3) designs with a trivial automorphism group (see [25]), we conclude that up to isomorphism there are at least 5421 symmetric (45,12,3) designs. 4. Ternary codes from symmetric (45,12,3) designs The code CF (D) of a design D = (P,B,I) over the finite field F is the space spanned by the incidence vectors of the blocks over F. If Q is any subset of the point set P, then we will denote the incidence vector of Q by vQ. Thus CF (D) = 〈vB |B ∈B〉, and is a subspace of FP, the full vector space of functions from P to F . The following theorem, that can be found in [2], shows that the code CF (D) over a field F of characteristic p is not interesting if p does not divide the order of D. In Theorem 4.2 rankp(D) denotes the dimension of CF (D), and j denotes the all-one vector. 148 D. Crnković et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 145–154 Table 3. Symmetric (45,12,3) designs with nontrivial automorphisms |Aut(D)| Structure of Aut(D) no. designs |Aut(D)| Structure of Aut(D) no. designs 51840 PSp(4, 3) : Z2 1 45 Z15 ×Z3 1 19440 (E81 : SL(2, 5)) : Z2 1 36 S3 ×S3 4 1296 E27 : (S4 ×Z2) 1 36 E9 : Z4 1 486 E81 : Z6 1 36 Z2 × (E9 : Z2) 1 486 E81 : S3 1 32 Z4 : Q8 1 432 ((S3 ×S3) : Z2)×S3 2 30 Z5 ×S3 1 360 (Z15 ×Z3) : Z8 1 27 E27 11 324 (E27 : Z3) : E4 1 27 Z9 : Z3 6 324 (E27 : Z3) : E4 1 27 E9 : Z3 4 216 (Z3 ×S3 ×S3) : Z2 3 24 Z3 ×Q8 1 216 (E9 : Z4)×S3 2 20 Z5 : Z4 1 216 S3 ×S3 ×S3 2 20 Z5 : Z4 1 192 (E4 ×Q8) : S3 2 18 Z3 ×S3 87 162 E27 : Z6 8 18 Z6 ×Z3 4 162 E27 : S3 5 18 E9 : Z2 4 162 E27 : S3 1 16 QD16 7 162 S3 × (E9 : Z3) 1 16 Z2 ×D8 2 144 (E9 : Z8) : Z2 2 16 (Z4 ×Z2) : Z2 1 108 S3 × (E9) : Z2) 4 15 Z15 2 108 E27 : Z4 2 12 D12 65 108 E27 : E4 1 11 Z11 1 108 Z3 ×S3 ×S3 1 9 E9 213 81 E27 : Z3 4 8 D8 12 81 E27 : Z3 1 8 Q8 7 64 (E4.(Z4 ×Z2)) : Z2 1 8 Z8 4 64 ((Z2 ×Q8) : Z2) : Z2 1 8 E8 2 54 E27 : Z2 24 8 Z4 ×Z2 2 54 E27 : Z2 9 6 S3 446 54 (Z9 : Z3) : Z2 6 6 Z6 104 54 E9 ×S3 6 5 Z5 4 54 E9 : Z6 3 4 E4 128 48 (Z3 ×Q8) : Z2 3 4 Z4 71 48 Z2 ×S4 1 3 Z3 1051 48 (Z4 ×Z4) : Z3 1 2 Z2 1931 Theorem 4.1. Let D = (P,B,I) be a nontrivial 2-(v,k,λ) design of order n. Let p be a prime and let F be a field of characteristic p, where p does not divide n. Then rankp(D) ≥ (v − 1) with equality if and only if p divides k; in the case of equality we have that CF (D) = 〈j〉⊥ and otherwise CF (D) = FP. Since the order of a symmetric (45,12,3) design is 9, we consider only the ternary codes of the constructed designs, i.e. codes over the field of order 3. The ternary codes of the 4285 symmetric 149 D. Crnković et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 145–154 (45,12,3) designs with nontrivial automorphisms are divided in 1005 equivalence classes. In Table 4 we give information about code parameters and orders of automorphism groups of representatives of equivalence classes, where the definitions of automorphisms and equivalence of codes are the same as in Magma [4]. The following theorem states that all the codes obtained are self-orthogonal. Theorem 4.2. Let D be a symmetric (45,12,3) design and C(D) be the ternary code of the design D. Then the code C(D) is self-orthogonal, and j ∈ C(D)⊥. Proof. The code C(D) is spanned by the rows of the row-point incidence matrix of D. Since each row of D has 12 points, and any two blocks intersect in 3 points, the code C(D) is self-orthogonal. It is obvious that j ∈ C(D)⊥, because each row of the design D consist of 12 points. Table 4. Ternary codes of the symmetric (45,12,3) designs with nontrivial automorphisms Parameters (|Aut(C)|, no. of inequivalent codes) [45, 22, 9] (11,1) [45, 21, 6] (60466176,1), (5832,1), (2592,1), (1944,1), (216,1), (108,1), (24,3), (12,1), (9,8), (8,4), (6,3), (4,10), (3,4), (2,19) [45, 20, 12] (2,3) [45, 20, 9] (15,1), (9,8), (6,4), (3,7), (2,2) [45, 20, 6] (45349632,1), (31104,1), (23328,1), (11664,1), (10368,1), (5832,1), (3888,2), (1944,2), (1152,1),(972,1), (648,2), (324,3), (288,1), (216,1), (162,5), (108,2), (72,6), (54,4), (36,10), (27,3), (24,11), (18,1), (12,34), (9,5), (8,6), (6,7), (5,2), (4,59), (3,1), (2,139) [45, 19, 12] (64,1), (32,1), (4,1), (2,1) [45, 19, 9] (162,1), (81,4), (54,2), (27,2), (18,1), (9,6), (4,1), (3,4) [45, 19, 6] (226748160,1), (52488,1), (23328,1), (17496,1), (11664,1), (5832,3), (4608,1), (1944,1), (1296,1), (972,1), (648,1), (486,2), (324,1), (288,2), (216,2), (108,3), (72,7), (54,4), (36,20), (24,9), (20,1), (18,9), (16,3), (12,37), (9,2), (8,6), (6,32), (4,51), (3,16), (2,132) [45, 18, 12] (20,1) [45, 18, 9] (18,2), (9,1), (6,2), (2,2) [45, 18, 6] (209952,1), (52488,1), (23328,1), (8748,1), (7290,1), (5832,1), (1944,2), (1296,3), (432,1), (324,3), (216,2), (162,2), (108,6), (72,7), (54,4), (48,3), (36,14), (27,1), (24,1), (18,11), (16,1), (12,18), (8,5), (6,22), (4,16), (3,8), (2,34) [45, 17, 12] (192,2), (48,2) [45, 17, 9] (360,1), (81,1) [45, 17, 6] (69984,1), (3888,1), (2916,1), (1944,2), (486,1), (432,1), (324,6), (288,1), (216,1), (162,1), (144,1), (108,3), (54,1), (36,3), (18,1), (16,2), (12,4), (9,1), (8,1), (6,3), (4,1), (2,1) [45, 16, 9] (486,1), (324,1) [45, 16, 6] (972,1), (432,1), (216,1), (108,1) [45, 15, 12] (51840,1) [45, 15, 9] (19440,1) In Table 5 we give information about the dual codes of the codes presented in Table 4. According to [15] and [26], the [45,28,8] code has the greatest minimum distance among the known ternary [45,28] codes. Further, the best known ternary [45,30] code has minimum distance 7, hence the [45,30,6] code has minimum distance one less than the best known code. A linear code whose dual code supports the blocks of a t-design admits one of the simplest decoding algorithms, majority logic decoding (see [28]). If a codeword x = (x1, . . . ,xn) ∈ C is sent over a communication channel, and a vector y = (y1, . . . ,yn) is received, for each symbol yi a set of values 150 D. Crnković et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 145–154 y (1) i , . . . ,y (ri) i of ri linear functions defined by the blocks of the design are computed, and yi is decoded as the most frequent among the values y(1)i , . . . ,y (ri) i . The following result have been obtained by Rudolph [28]. Theorem 4.3. If C is a linear [n,k] code such that C⊥ contains a set S of vectors of weight w whose supports are the blocks of a 2-(n,w,λ) design, the code C can correct up to e = ⌊ r + λ− 1 2λ ⌋ errors by majority logic decoding, where r = λn−1 w−1. Consequently, the codes listed in Table 5 can correct up to two errors by majority logic decoding. Table 5. Dual codes of ternary codes of the symmetric (45,12,3) designs with nontrivial auto- morphisms Parameters (|Aut(C)|, no. of inequivalent codes) [45, 30, 6] (51840,1), (19440,1) [45, 29, 6] (972,1), (486,1), (432,1), (324,1), (216,1), (108,1) [45, 28, 8] (48,1) [45, 28, 6] (69984,1), (3888,1), (2916,1), (1944,2), (486,1), (432,1), (360,1), (324,6), (288,1), (216,1), (192,2), (162,1), (144,1), (108,3), (81,1), (54,1), (48,1), (36,3), (18,1), (16,2), (12,4), (9,1), (8,1), (6,3), (4,1), (2,1) [45, 27, 6] (209952,1), (52488,1), (23328,1), (8748,1), (7290,1), (5832,1), (1944,1), (1296,3), (432,1), (324,3), (216,2), (162,2), (108,6), (72,7), (54,4), (48,3), (36,14), (27,1), (24,1), (20,1), (18,13), (16,1), (12,18), (9,1), (8,5), (6,24), (4,16), (3,8), (2,36) [45, 26, 8] (3,2) [45, 26, 6] (226748160,1), (52488,1), (23328,1), (17496,1), (11664,1), (5832,1), (4608,1), (1944,1), (1296,1), (972,1), (648,1),(486,2), (324,1), (288,2), (216,2), (162,1), (108,3), (81,4), (72,7), (64,1), (54,6), (36,20), (32,1), (27,2), (24,9), (20,1), (18,10), (16,3), (12,37), (9,8), (8,6), (6,32), (4,53), (3,18), (2,133) [45, 25, 8] (15,1), (2,2), (3,1) [45, 25, 6] (45349632,1), (31104,1), (23328,1), (11664,1), (10368,1), (5832,1), (3888,2), (1944,2), (1152,1), (972,1), (648,2), (324,3), (288,1), (216,1), (162,5), (108,2), (72,6), (54,4), (36,10), (27,3), (24,11), (18,1), (12,34), (9,13), (8,6), (6,11), (5,2), (4,59), (3,7), (2,142) [45, 24, 6] (60466176,1), (5832,1), (2592,1), (1944,1), (216,1), (108,1), (24,3), (12,1), (9,8), (8,4), (6,3), (4,10), (3,4), (2,19) [45, 23, 9] (11,1) 5. On k-geodetic graphs from symmetric (45, 12, 3) designs In this section we present results concerning 3-geodetic (trigeodetic) graphs. We prove that k- geodetic graphs constructed from mutually non-isomorphic designs are mutually non-isomorphic. For applications of k-geodetic graphs in the topological design of computer networks the reader may consult [13]. For further reading on k-geodetic graphs we refer the reader to [27] and [29]. For every 2-(v,k,λ) design D with replication number r and b blocks it is possible to construct k−connected biregular block K∗v (r,k,λ) (a block is a graph with vertex connectivity > 1) of diameter 4 151 D. Crnković et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 145–154 or 5 with vertex degrees r and k, in which there are at most µ paths of minimum length between any pair of vertices, where µ = max{max{|Bi ∩Bj| : i,j = 1, 2, . . . ,b, i 6= j} , λ} , B1,B2, . . . ,Bb being blocks of the design (see [29]). K∗v (r,k,λ) has v(r + 1) vertices and vr(k+1) 2 edges. If D is a symmetric design then K∗v (r,k,λ) is k−regular graph in which there are at most λ paths of minimum length between each pair of vertices. Graphs in which every pair of nonadjacent vertices has a unique path of minimum length between them are called geodetic graph, bigeodetic graphs are graphs in which each pair of nonadjacent vertices has at most two paths of minimum length between them and graphs in which each pair of nonadjacent vertices has at most k paths of minimum length between them are called k-geodetic graphs (see [13], [29]). We follow the construction of K∗v (r,k,λ) from a 2-(v,k,λ) design given in [29]. If Bi = {Pi1, . . . Pik}, 1 ≤ i ≤ b, is a block of a design D, then {xi1i, . . . ,xiki} are vertices of the complete graph (Kk)i. Graphs (Kk)i , 1 ≤ i ≤ b, together with v vertices xi0, 1 ≤ i ≤ v, xi0 and xst being adjacent if i = s, form the graph K∗v (r,k,λ) for the design D. The adjacency matrix of a graph K∗v (r,k,λ) is given as follows A =   (Jk − Ik) 0k . . . 0k M1 0k (Jk − Ik) · · · 0k M2 ... ... ... ... ... 0k 0k · · · (Jk − Ik) Mb MT1 M T 2 . . . M T b 0v   , where Mi = [mr,s], 1 ≤ i ≤ b, are k × v matrices with m1,i1 = m2,i2 = ... = mk,ik = 1 for Bi = {Pi1, . . . Pik}, 1 ≤ i1 ≤ i2 ≤ ··· ≤ ik ≤ v and mr,s = 0 otherwise, 0k is the k ×k zero-matrix, Jk is the k ×k all-one matrix, and Ik is the k ×k identity matrix. Rows of Mi, 1 ≤ i ≤ b, are labeled with xi1i, ...,xiki, and columns of Mi, 1 ≤ i ≤ b, are labeled with x10, ...,xv0. The number of columns labeled with xs0, 1 ≤ s ≤ v in which matrices Mi and Mj both have an entry 1 is equal to |Bi ∩Bj|, since in the column xs0 there is an entry 1 in both matrices if and only if Ps ∈ Bi ∩Bj. Moreover, the matrix Mi is determined by the ith row of the incidence matrix IM = [di,s] of the design D. Vice versa, the ith row of the incidence matrix IM = [di,s] is determined by the matrix Mi, putting di,s = 1 if there exists a row of Mi having 1 on the position xs0. Theorem 5.1. Let D1 and D2 be 2-(v,k,λ) designs. Then the corresponding graphs K∗v (r,k,λ)1 and K∗v (r,k,λ) 2 are isomorphic if and only if the designs D1 and D2 are isomorphic. Proof. Let D1 = (P1,B1,I1) and D2 = (P2,B2,I2) be 2-(v,k,λ) designs and α be an isomorphism from D1 onto D2. Then there exists unique isomorphism β between the corresponding graphs K∗v (r,k,λ)1 and K∗v (r,k,λ) 2 that satisfy( P1s α = P 2 t ∧B 1 i α = B 2 j ) ⇒ ( (Kk) 1 i β = (Kk) 2 j ∧x 1 s0β = x 2 t0 ) , where 1 ≤ s ≤ v, 1 ≤ i ≤ b. Conversely, each isomorphism from the graph K∗v (r,k,λ) 1 onto K∗v (r,k,λ) 2 induces unique isomor- phism from the design D1 onto D2. To prove this statement it is crusial to show that an isomorphism from K∗v (r,k,λ) 1 onto K∗v (r,k,λ) 2 maps vertices {x110, . . . ,x1v0} of K∗v (r,k,λ)1 onto vertices {x210, . . . ,x2v0} of K∗v (r,k,λ) 2. If the designs D1 and D2 are not symmetric, then r 6= k and since the vertices x110, . . . ,x1v0 and x210, . . . ,x 2 v0 have degree r and the other vertices of K ∗ v (r,k,λ) 1 and K∗v (r,k,λ) 2 have degree k, it is clear that an isomorphism from K∗v (r,k,λ) 1 onto K∗v (r,k,λ) 2 maps the set {x110, . . . ,x1v0} onto {x210, . . . ,x2v0}. 152 D. Crnković et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 145–154 If D1 and D2 are symmetric designs then r = k. A vertex x1i0 and a vertex adjacent to x 1 i0 have no common neighbour, while a vertex that do not belong to {x110, . . . ,x1v0} has k − 2 commmon neighbours with any of its neighbour. Similarly, a vertex x2i0 and a vertex adjacent to him have no common neighbour, while a vertex that do not belong to {x210, . . . ,x2v0} has k − 2 commmon neighbours with any of its neighbour. Hence, we conclude that {x110, . . . ,x1v0} is mapped onto {x210, . . . ,x2v0}. So, an isomorphism from K∗v (r,k,λ) 1 onto K∗v (r,k,λ) 2 maps (Kk) 1 i onto (Kk) 2 j, and M 1 i onto M 2 j, and it induces unique isomorphism from the design D1 onto D2. Graphs K∗45(12, 12, 3) constructed from symmetric (45,12,3) designs are 12-connected and 12-regular graphs of diameter 4 with 585 vertices and 3510 edges. For each pair of nonadjacent vertices there are at most three paths of minimum length between them. From all known triplanes of order nine one can obtain 5421 non-isomorphic graphs K∗45(12, 12, 3), since non-isomorphic designs produce non-isomorphic trigeodetic graphs. The following theorem, which is proved in [11], shows that Table 3 gives information on automorphism groups of all trigeodetic graphs constructed from the symmetric (45,12,3) designs with nontrivial automorphisms, and that there are at least 1136 trigeodetic graphs K∗45(12, 12, 3) having trivial group as the full automorphism group. Theorem 5.2. Let D be a 2-(v,k,λ) design. Then the full automorphism group of D is isomorphic to the full automorphism group of the corresponding k-geodetic graph K∗v (r,k,λ). All symmetric (45,12,3) designs admitting nontrivial automorphisms can be found at http://www.math.uniri.hr/∼sanjar/structures/. References [1] R. W. Ahrens, G. Szekeres, On a combinatorial generalization of the 27 lines associated with a cubic surface, J. Austral. Math. Soc. 10 (1969) 485–492. [2] E. F. Assmus Jr., J. D. Key, Designs and Their Codes, Cambridge University Press, Cambridge, 1992. [3] T. Beth, D. Jungnickel, H. Lenz, Design Theory, 2nd Edition, Cambridge University Press, Cam- bridge, 1999. [4] W. Bosma, J. Cannon, C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24(3-4) (1997) 235–265. [5] V. Ćepulić, On symmetric block designs (45,12,3) with automorphisms of order 5, Ars Combin. 37 (1994) 33–48. [6] C. J. Colbourn, J. F. Dinitz (Eds.), The CRC Handbook of Combinatorial Designs, 2nd Edition, CRC Press, Boca Raton, 2007. [7] K. Coolsaet, J. Degraer, E. Spence, The strongly regular (45, 12, 3, 3) graphs, Electron. J. Combin. 13(1) (2006) Research Paper 32, 1–9. [8] D. Crnković, B. G. Rodrigues, S. Rukavina, L. Simčić, Ternary codes from the strongly regular (45,12,3,3) graphs and orbit matrices of 2-(45,12,3) designs, Discrete Math. 312(20) (2012) 3000– 3010. [9] D. Crnković, S. Rukavina, Construction of block designs admitting an abelian automorphism group, Metrika 62(2-3) (2005) 175–183. [10] D. Crnković, S. Rukavina, On some symmetric (45, 12, 3) and (40, 13, 4) designs, J. Comput. Math. Optim. 1(1) (2005) 55–63. [11] D. Crnković, S. Rukavina, L. Simčić, On triplanes of order twelve admitting an automorphism of order six and their binary and ternary codes, Util. Math., to appear. 153 http://www.ams.org/mathscinet-getitem?mr=269524 http://www.ams.org/mathscinet-getitem?mr=269524 http://dx.doi.org/10.1006/jsco.1996.0125 http://dx.doi.org/10.1006/jsco.1996.0125 http://www.ams.org/mathscinet-getitem?mr=1282543 http://www.ams.org/mathscinet-getitem?mr=1282543 http://www.ams.org/mathscinet-getitem?mr=2212505 http://www.ams.org/mathscinet-getitem?mr=2212505 http://dx.doi.org/10.1016/j.disc.2012.06.012 http://dx.doi.org/10.1016/j.disc.2012.06.012 http://dx.doi.org/10.1016/j.disc.2012.06.012 http://dx.doi.org/10.1007/s00184-005-0407-y http://dx.doi.org/10.1007/s00184-005-0407-y http://www.ams.org/mathscinet-getitem?mr=2128940 http://www.ams.org/mathscinet-getitem?mr=2128940 D. Crnković et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 145–154 [12] U. Dempwolff, Primitive rank 3 groups on symmetric designs, Des. Codes Cryptogr. 22(2) (2001) 191–207. [13] C. E. Frasser, k-geodetic Graphs and Their Application to the Topological Design of Computer Networks, Argentinian Workshop in Theoretical Computer Science, 28 JAIIO-WAIT ’99 (1999) 187– 203. [14] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.7.2; 2013. (http://www.gap-system.org) [15] M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Online available at http://www.codetables.de, Accessed on 2014-03-11. [16] Z. Janko, Coset enumeration in groups and constructions of symmetric designs, Combinatorics ’90 (Gaeta, 1990), Ann. Discrete Math. 52 (1992) 275–277. [17] P. Kaski, P. R. J. Östergård, Classification Algorithms for Codes and Designs, Springer, Berlin, 2006. [18] P. Kaski and P. R. J. Östergård, There are exactly five biplanes with k = 11, J. Combin. Des. 16(2) (2008) 117–127. [19] T. Kölmel, Einbettbarkeit symmetrischer (45,12,3) Blockplaene mit fixpunktfrei operierenden Auto- morphismen, Heidelberg, 1991. [20] C. W. H. Lam, G. Kolesova, L. H. Thiel, A computer search for finite projective planes of order 9, Discrete Math. 92(1-3) (1991) 187–195. [21] E. Lander, Symmetric Designs: An Algebraic Approach, Cambridge University Press, Cambridge, 1983. [22] R. Mathon, A. Rosa, 2-(v,k,λ) Designs of Small Order, in: Handbook of Combinatorial Designs, 2nd ed., C.J. Colbourn, J.H. Dinitz (Editors), Chapman & Hall/CRC, Boca Raton (2007) 25–58. [23] R. L. MacFarland, A family of difference sets in non-cyclic groups, J. Combin. Theory Ser. A 15 (1973) 1–10. [24] V. Mandekić-Botteri, On symmetric block designs (45,12,3) with involutory automorphism fixing 15 points, Glas. Mat. Ser. III 36(56)(2) (2001) 193–222. [25] R. Mathon, E. Spence, On 2-(45,12,3) designs, J. Combin. Des. 4(3) (1996) 155–175. [26] MinT, Dept. of Mathematics, University of Salzburg, The online database for optimal parame- ters of (t,m,s)-nets, (t,s)-sequences, orthogonal arrays, linear codes, and OOAs, Online available at http://mint.sbg.ac.at/index.php, Accessed on 2014-03-11. [27] R. M. Ramos, J. Sicilia, M. T. Ramos, A generalization of geodetic graphs: K-geodetic graphs, Investigacion Operativa 6 (1998) 85–101. [28] L. Rudolph, A class of majority logic decodable codes, IEEE Trans. Inform. Theory 13(2) (1967) 305–307. [29] N. Srinivasan, J. Opatrný, V. S. Alagar, Construction of geodetic and bigeodetic blocks of connec- tivity k ≥ 3 and their relation to block designs, Ars Combin. 24 (1987) 101–114. [30] L.H. Soicher, DESIGN - a GAP package, Version 1.6, 23/11/2011. (http://www.gap- system.org/Packages/design.html) 154 http://dx.doi.org/10.1023/A:1008373207617 http://dx.doi.org/10.1023/A:1008373207617 http://www.gap-system.org http://www.gap-system.org http://www.codetables.de http://www.codetables.de http://dx.doi.org/10.1016/S0167-5060(08)70919-1 http://dx.doi.org/10.1016/S0167-5060(08)70919-1 http://dx.doi.org/10.1002/jcd.20145 http://dx.doi.org/10.1002/jcd.20145 http://dx.doi.org/10.1016/0012-365X(91)90280-F http://dx.doi.org/10.1016/0012-365X(91)90280-F http://dx.doi.org/10.1016/0097-3165(73)90031-9 http://dx.doi.org/10.1016/0097-3165(73)90031-9 http://www.ams.org/mathscinet-getitem?mr=1884442 http://www.ams.org/mathscinet-getitem?mr=1884442 http://dx.doi.org/10.1002/(SICI)1520-6610(1996)4:3<155::AID-JCD1>3.0.CO;2-E http://mint.sbg.ac.at/index.php http://mint.sbg.ac.at/index.php http://mint.sbg.ac.at/index.php http://dx.doi.org/10.1109/TIT.1967.1053994 http://dx.doi.org/10.1109/TIT.1967.1053994 http://www.ams.org/mathscinet-getitem?mr=0917965 http://www.ams.org/mathscinet-getitem?mr=0917965 http://www.gap-system.org/Packages/design.html http://www.gap-system.org/Packages/design.html Introduction Outline of the construction Classification of symmetric (45,12,3) designs with nontrivial automorphisms Ternary codes from symmetric (45,12,3) designs On k-geodetic graphs from symmetric (45,12,3) designs References