Sie können Operatoren mit Ihrer Suchanfrage kombinieren, um diese noch präziser einzugrenzen. Klicken Sie auf den Suchoperator, um eine Erklärung seiner Funktionsweise anzuzeigen.
Findet Dokumente, in denen beide Begriffe in beliebiger Reihenfolge innerhalb von maximal n Worten zueinander stehen. Empfehlung: Wählen Sie zwischen 15 und 30 als maximale Wortanzahl (z.B. NEAR(hybrid, antrieb, 20)).
Findet Dokumente, in denen der Begriff in Wortvarianten vorkommt, wobei diese VOR, HINTER oder VOR und HINTER dem Suchbegriff anschließen können (z.B., leichtbau*, *leichtbau, *leichtbau*).
Der Artikel untersucht additive kombinatorische Designs, mit besonderem Fokus auf Steiner 2-Designs und deren Verallgemeinerungen zu -Designs. Es führt das Konzept additiver Designs ein, bei denen die Punktzahl eine Teilmenge einer abelschen Gruppe ist und jeder Block ein Nullsummenspiel darstellt. Die Autoren untersuchen die Beschränkungen und Eigenschaften dieser Entwürfe und stellen fest, dass zusätzliche Beschränkungen zwar die Konstruktion und den Nachweis erleichtern, aber auch die Konstruktion erschweren können. Der Artikel präsentiert mehrere neue Konstruktionen additiver kombinatorischer Designs, darunter eine unendliche Klasse streng additiver Designs und ein sporadisches additives Steiner 2-Design. Es führt auch die Vorstellung von kosettierten Designs ein und beweist ihre Additivität, was zur Konstruktion mehrerer unendlicher Klassen von additiven Designs führt. Die Autoren diskutieren die Existenz additiver Designs für verschiedene Werte von v und k und liefern detaillierte Rezepte und Beispiele. Der Artikel untersucht auch den Einsatz von Differenzmethoden und Skolem-Sequenzen bei der Konstruktion additiver Designs und stellt mehrere offene Probleme und Richtungen für zukünftige Forschungen vor.
KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
Abstract
A \(2-(v, k, \lambda )\) design is additive if, up to isomorphism, the point set is a subset of an abelian group G and every block is zero-sum. This definition was introduced in Caggegi et al. (J Algebr Comb 45:271-294, 2017) and was the starting point of an interesting new theory. Although many additive designs have been constructed and known designs have been shown to be additive, these structures seem quite hard to construct in general, particularly when we look for additive Steiner 2-designs. One might generalize additive Steiner 2-designs in a natural way to graph decompositions as follows: given a simple graph \(\Gamma \), an additive \((K_v,\Gamma )\)-design is a decomposition of the graph \(K_v\) into subgraphs (blocks) \(B_1,\dots ,B_t\) all isomorphic to \(\Gamma \), such that the vertex set \(V(K_v)\) is a subset of an abelian group G, and the sets \(V(B_1), \dots , V(B_t)\) are zero-sum in G. In this work we begin the study of additive \((K_v,\Gamma )\)-designs: we develop different tools instrumental in constructing these structures, and apply them to obtain some infinite classes of designs and many sporadic examples. We will consider decompositions into various graphs \(\Gamma \), for instance cycles, paths, and k-matchings. Similar ideas will also allow us to present here a sporadic additive 2-(124, 4, 1) design.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
In this work we will consider \(2-(v,k,1)\)-designs, also called Steiner 2-designs, and their generalization to \((K_v,\Gamma )\)-designs, that are decompositions of the edges of the complete graph on v vertices \(K_v\) into copies of a graph \(\Gamma \). We will study additive designs, a class of designs subject to a particular constraint.
From the very start of design theory, designs satisfying extra properties have often been considered; for instance, one may look for a structure having a given automorphism group, and this requirement may actually help in constructing it, or in proving results about it.
Anzeige
On the other hand, imposing some constraints might make the designs very difficult to construct: one example is q-analogs of Steiner 2-designs, i.e., Steiner 2-designs over \(\mathbb {F}_q\) or \(2-(v,k,1;q)\)-designs. Here the very strong requirement is that the points of the design are the points of the \((v-1)\)-dimensional projective space over \(\mathbb {F}_q\) and the points in each block form a subspace of dimension \(k-1\). There is only one set of parameters for which nontrivial such designs are known to exist, and that gives the celebrated \(2-(13,3,1;2)\)-design in [8].
Another quite recent example of imposing a strong constraint on the considered structures is that of additive designs: a \(2-(v, k, \lambda )\) design is additive if, up to isomorphism, the point set is a subset of an abelian group G and every block is zero-sum. Additive \(2-(v, k, \lambda )\) designs were introduced by Caggegi, Falcone and Pavone in [18], and have since been studied in the last years (see [13, 14, 19, 22, 28]). Note that additive designs have interesting connections with several branches of discrete mathematics such as coding theory and additive combinatorics, and that the usage of zero-sum blocks in the construction of designs is frequent (see, e.g., [9, 10, 21, 27, 34]). Also in this case, the property we request makes the construction of these designs a hard problem in general, particularly so when \(\lambda =1\): the known additive Steiner 2-designs either come from the geometry (the point-line designs of AG(n, q) and PG(n, q) have been proved to be additive in [18] and [14]), or have a huge number of points (the super-regular designs constructed in [13]). Designs over \(\mathbb {F}_q\) are also additive (see [14]), so that another example is given by the mentioned \(2-(13,3,1;2)\)-design in [8]. The only other known additive Steiner 2-design is the sporadic \(2-(124,4,1)\)-design we present here in Sect. 5.2.
Note that we may think of a \(2-(v,k,1)\) design as a decomposition of \(K_v\) into cliques of size k, i.e., into copies of the complete graph \(K_k\); so that the concept of a graph decomposition may be seen as a generalization of block designs. On the other hand, some graph decompositions are oftentimes easier to construct and study. For these reasons in [15] the authors considered q-analogs of graph decompositions, that is decompositions of a graph K, with vertex set the points of a projective space \(\mathbb {P}\) over \(\mathbb {F}_q\), into copies of a graph \(\Gamma \) each of which has a subspace of \(\mathbb {P}\) as vertex set, and called these “\(2-(v, \Gamma , 1)\) designs over \(\mathbb {F}_q\)”. This generalization allowed them to construct new examples, prove some new results and obtain more insight that could help in studying 2-designs over \(\mathbb {F}_q\). Still, constructing \(2-(v, \Gamma , 1)\) designs over \(\mathbb {F}_q\) turns out to be also a hard problem, and no infinite class of these designs is known.
The main aim of this work is to consider and study a similar generalization for additive designs.
Anzeige
Definition 1.1
A \(\Gamma \)-decomposition of a graph K is G-additive if, up to isomorphism, the vertex set V(K) is a subset of an abelian group G and the vertex set of every block is zero-sum in G. When \(K=K_v\), we speak of an additive \((K_v,\Gamma )\)-design.
In this work, we begin the study of additive \((K_v,\Gamma )\)-designs. We show that, although moving from “classic” block designs to graph decompositions allows us to build many examples, both of infinite classes of additive combinatorial designs and of more sporadic examples, the problem of constructing these structures remains a challenging one. Some of the general methods exposed in the paper helped us in constructing a new sporadic additive \(2-(124,4,1)\)-design.
The paper is organized as follows: after establishing the basic definitions and first results in Sect. 2, we recall in Sect. 3 some difference methods useful in the construction of \((K_v,\Gamma )\)-designs. In Sect. 4 we obtain an infinite class of strictly additive \((K_{mk},C_k)\)-designs (see Definition 2.1 below) by adapting to graph decompositions ideas introduced for block designs in [13]. We then develop in Sect. 5 a general technique to ensure additivity of the constructed designs; this strategy is applied in the rest of the section to obtain a great variety of additive combinatorial designs, in particular the sporadic additive \(2-(124,4,1)\)-design previously mentioned. In Sect. 6 we introduce coseted designs and prove their additivity: we then construct many examples and some infinite classes of these designs, proving for instance the existence of another infinite class of \((K_v,C_k)\)-designs. The notion of coseted design is especially exploited in Sect. 7 which studies additive \((K_{2v},M_{2k})\)-designs, that is, decompositions of \(K_{2v}\) into graphs consisting of k pairwise disjoint edges (k-matchings). Their existence is proved whenever k divides v and also for \(2v=2mk+k+1\) with \(m>0\) and \(k\ge 3\) odd.
2 First examples and some elementary results
For general background on design theory and, more generally, on graph decompositions, we refer to [4, 20]. We denote by \(C_k\) the cycle on k vertices, with \(P_k\) the path on k vertices (having \(k-1\) edges), and by \(M_{2k}\) the k-matching, i.e., the graph consisting of k pairwise disjoint edges. By \([x_0,x_1,\dots ,x_{k-1}]\) we mean the path whose edges are \(\{x_i,x_{i+1}\}\) for \(0\le i\le k-2\). By \((x_0,x_1,\dots ,x_{k-1})\) we mean the cycle obtained from the path above by adding the edge \(\{x_{k-1},x_0\}\).
There are obvious necessary conditions for the existence of \((K_v,C_k)\)-designs, namely v must be odd, \(3 \le k \le v\) and k must divide \(\left( {\begin{array}{c}v\\ 2\end{array}}\right) \): pairs (v, k) satisfying these conditions are called admissible. The existence of a \((K_v,C_k)\)-design for all admissible values has been shown by Alspach, Gavlas and Šajna [1, 31]; see also [11] for an alternative proof in the odd-cycle case. Also for \((K_v,P_k)\)-designs, existence is known (see Tarsi [33]) for all admissible values, that is, whenever \(k\le v\) and \(k-1\) divides \(\left( {\begin{array}{c}v\\ 2\end{array}}\right) \).
The following definitions used for “classic” block designs can be extended to \((K_v,\Gamma )\)-designs.
Definition 2.1
A G-additive \((K_v,\Gamma )\)-design is strictly G-additive if \(V(K_v)=G\) and almost strictly G-additive if \(V(K_v)=G\setminus \{0\}\).
Given a prime power q we denote by \(\mathbb {F}_q\), EA(q) and \(\mathbb {F}_q^*\) the finite field of order q, its additive group and its multiplicative group, respectively. If q is odd, \(\mathbb {F}_q^\Box \) denotes the group of non-zero squares of \(\mathbb {F}_q\). We will repeatedly use the following fact, that is Fact 2.1 in [13]:
Fact 2.2
If q is a prime power, every coset of a non-trivial subgroup of \(\mathbb {F}_q^*\) (thus, in particular, every non-trivial subgroup of \(\mathbb {F}_q^*\)) is zero-sum.
To break the ice, we start by giving two concrete, easy but not trivial examples of strictly EA(9)-additive \((K_9,\Gamma )\)-designs with \(\Gamma \) the 5-path and the 4-cycle. In order to improve the readability, every element (x, y) of EA(9) will be simply denoted by xy.
Example 2.3
The following nine 5-paths are the blocks of a strictly EA(9)-additive \((K_9,P_5)\)-design:
The additive designs above have been easily found using a computer. It is possible to give more concise presentations of G-additive designs of the same kinds if we do not demand that G is EA(9).
Example 2.4
A \(\mathbb {F}_{19}\)-additive \((K_9,P_5)\)-design with vertex set \(\mathbb {F}_{19}^\Box \):
The additive designs of Example 2.4 have been found by hand using difference methods as it will be explained in Sect. 4. It would be natural to prefer them rather than those of Example 2.3 since they are more elegant. Yet, as we will show later in this section, the strict additivity of the first ones allows to obtain, recursively, infinitely many other additive designs not obtainable with those of Example 2.4.
It was proved in [18] that if v is not a power of 3 nor a Mersenne number, then no additive 2-(v, 3, 1) design (that is a \((K_v,C_3)\)-design) exists. This result was not trivial at all. Here are two other very elementary non-existence results.
Proposition 2.5
No additive \((K_v,P_3)\)-design exists.
Proof
Assume that there exists a G-additive \((K_v,P_3)\)-design. Take an arbitrary block \(B=[a,b,c]\) and let \(B'\) be the block where the edge \(\{a,c\}\) appears. We have either \(B'=[a,c,d]\) or \(B'=[c,a,d]\) for some element \(d\in G\). Given that B and \(B'\) are zero-sum we have \(c=-a-b\) and \(d=-a-c\) which give \(d=b\). Thus we have either \(B'=[a,c,b]\) or \(B'=[c,a,b]\). This is absurd since the block \(B'\) would share an edge with B, that is \(\{b,c\}\) in the first case or \(\{a,b\}\) in the second. \(\square \)
A subgraph \(\Gamma \) of a complete graph \(K_v\) is spanning or almost spanning if \(V(\Gamma )\) is the whole vertex set of \(K_v\) or misses exactly one vertex of \(K_v\), respectively.
Proposition 2.6
If \(\Gamma \) is an almost spanning subgraph of \(K_v\), then no additive \((K_v,\Gamma )\)-design exists.
Proof
Let V be the vertex set of a G-additive \((K_v,\Gamma )\)-design and let s be the sum of its elements in G. Given that a block B is a copy of \(\Gamma \) which is almost spanning, there is only one vertex of V not belonging to B. This vertex is forced to be s since B is zero-sum. It follows that the vertex s does not belong to any block of the design which is absurd. \(\square \)
On the contrary, every \((K_v,\Gamma )\)-design with \(\Gamma \) spanning is additive.
Proposition 2.7
If \(\Gamma \) is a spanning subgraph of \(K_v\), then every \((K_v,\Gamma )\)-design is additive.
Proof
Let \(\mathcal D\) be a design as in the statement. Observe that every abelian group of odd order is zero-sum whereas an abelian group of even order is zero-sum if and only if its Sylow 2-subgroup is not cyclic. Thus, for \(v\not \equiv 2\) (mod 4), we have at least one zero-sum group G of order v and we can label the vertices of \(K_v\) with the elements of this group obtaining in this way a strictly G-additive isomorphic copy of \(\mathcal D\). For \(v\equiv 2\) (mod 4) we can label the vertices of \(K_v\) with the elements of \(\mathbb {Z}_{v+1}\setminus \{0\}\) obtaining an almost strictly \(\mathbb {Z}_{v+1}\)-additive isomorphic copy of \(\mathcal D\). \(\square \)
Proposition 2.8
Assume that there exist a G-additive 2-(v, k, 1) design \((V,\mathcal{B})\) and a \((K_k,\Gamma )\)-design \(\mathcal D\) with \(\Gamma \) a spanning subgraph of \(K_k\). Then there exists a G-additive \((K_v,\Gamma )\)-design.
Proof
For each block \(B\in \mathcal{B}\) construct an isomorphic copy of \(\mathcal{D}\) with vertex set B, say \(\mathcal{D}(B)\). Then \(\mathcal{D}':=\bigcup _{B\in \mathcal{B}}\mathcal{D}(B)\) is a \((K_v,\Gamma )\)-design. Any block of \(\mathcal{D}(B)\) has vertex set B since \(\Gamma \) spans \(K_k\). Also, B is zero-sum in G since \((V,\mathcal{B})\) is G-additive. Hence every block of \(\mathcal{D}'\) is zero-sum, i.e., \(\mathcal{D}'\) is G-additive. \(\square \)
Exploiting the strict additivity of the point-line design of an affine geometry we can obtain the following.
Proposition 2.9
If there exists an EA(q)-additive \((K_q,\Gamma )\) design, then there exists an \(EA(q^n)\)-additive \((K_{q^n},\Gamma )\)-design for every positive integer n.
Proof
Let \(G=EA(q^n)\) and let \((G,\mathcal{L})\) be the 2-\((q^n,q,1)\) point-line design associated with the n-dimensional affine geometry over \(\mathbb {F}_q\). Let \(\{A_1,\dots ,A_t\}\) be the set of lines through 0 and note that each of them is a subgroup of G isomorphic to EA(q). Thus the assumption guarantees that there exists a strictly \(A_i\)-additive \((K_q,\Gamma )\)-design \(\mathcal{D}_i\) with vertex set \(A_i\) for \(1\le i\le t\). Given any \(L\in \mathcal{L}\), we have \(L=A_i+g\) for a suitable pair (i, g) and it is evident that \(\mathcal{D}(L):=\{B+g \ | \ B\in \mathcal{D}_i\}\) is a \((K_q,\Gamma )\)-design with vertex set L. Thus the set \(\mathcal{D}:=\{\mathcal{D}(L) \ | \ L\in \mathcal{L}\}\) is a \((K_{q^n},\Gamma )\)-design with vertex set G. The vertex set of any block of \(\mathcal{D}\) is a line of \(\mathcal{L}\) which is zero-sum since we already know that \((G,\mathcal{L})\) is strictly G-additive. We conclude that \(\mathcal{D}\) is strictly G-additive as well. \(\square \)
The above proposition together with Example 2.3 allows us to state the following.
Theorem 2.10
For any graph \(\Gamma \) which is either the 5-path or the 4-cycle, there exists a strictly additive \((K_{9^n},\Gamma )\)-design for all n.
As another application of Proposition 2.9, after checking that
is a strictly \(\mathbb {Z}_7\)-additive \((K_7,P_4)\)-design, we can state the following.
Theorem 2.11
There exists a strictly additive \((K_{7^n},P_4)\)-design for all n.
3 Difference packings
Apart from “small”designs obtained by computer as those of Example 2.3, almost all additive graph decompositions in this paper are obtained via some “difference methods”as those of Example 2.4. In this section, for the convenience of the reader, we briefly explain some of these methods.
Given a group G with operation \(\star \), we denote by \(G^+\) the set \(G \ \cup \ \{\infty \}\) where \(\infty \) is a symbol not in G, and we extend the operation \(\star \) to \(G^+\) by setting \(g\star \infty =\infty \star g=\infty \) for all \(g\in G\). In the special case (frequently considered in this paper) that G is a group of units of a commutative and unitary ring R, we agree to take \(\infty =0\).
If \(g\in G\) and B is a copy of \(\Gamma \) with vertices in G or \(G^+\), then \(B\star g\) will denote the copy of \(\Gamma \) obtained from B by replacing each vertex x with \(x\star g\). The G-stabilizer of B is the group of all \(g\in G\) for which \(B\star g=B\) whereas the G-orbit of B is the set of all distinct graphs of the form \(B\star g\).
We will say that a \((K_v,\Gamma )\)-design is G-regular (or \(G^+\)-rotational) if \(V(K_v)=G\) (or \(G^+\)) and every translation of G leaves it invariant, that is to say that the group of translations of G is an automorphism group of \(\mathcal D\). By a set of base blocks for a G-regular or \(G^+\)-rotational design \(\mathcal D\) we will mean a set of representatives for the G-orbits of the blocks of \(\mathcal D\). Also, by saying that a \((K_v,\Gamma )\)-design is cyclic or 1-rotational we will mean that it is \(\mathbb {Z}_v\)-regular or \(\mathbb {Z}_{v-1}^+\)-rotational, respectively.
In the following, the identity element of G and the inverse of an element \(g\in G\) will be denoted by e and \(g^\prime \), respectively.
We recall that if \(\Omega \) is a symmetric subset of \(G\setminus \{e\}\) (which means that \(\omega \in \Omega \) if and only if \(\omega ^\prime \in \Omega \)), the Cayley graph on G with connection set\(\Omega \) is the graph \(Cay[G:\Omega ]\) with vertex set G where \(\{x,y\}\) is an edge if and only if \(x\star y^\prime \in \Omega \). We will also consider the graph \(Cay[G^+:\Omega ]\) as the graph obtained from \(Cay[G:\Omega ]\) by adding the vertex \(\infty \) and all edges \(\{\infty ,g\}\) with \(g\in G\).
Generalizing the well-known notions of difference set, difference packing and difference family, we give the following definitions.
The list of differences of a copy B of \(\Gamma \) with vertices in G is the multiset \(\Delta B\) of all possible elements \(x\star y^\prime \) with (x, y) an ordered pair of adjacent vertices of B. In the special case that \(\Gamma \) is complete, V(B) is said to be a difference set when \(\Delta B\) is evenly distributed over the set of non-identity elements of G.
A \((G,\Gamma ,1)\)difference packing is a set \(\mathcal{F}=\{B_1,\dots ,B_t\}\) of copies of \(\Gamma \) (blocks) with vertices in G such that the multiset union \(\Delta \mathcal{F}:=\bigcup _{i=1}^t\Delta B_i\) does not have repeated elements. The blocks of such a difference packing gives rise to a \(\Gamma \)-decomposition of \(Cay[G:\Delta \mathcal{F}]\) given by \(\{B_i\star g \ | \ 1\le i\le t; g\in G\}\).
The difference leave of \(\mathcal F\) is the set L of all elements of G not covered by \(\Delta \mathcal{F}\). If \(\Gamma \) has size s, it is obvious that \(\Delta B_i\) has size 2s for every i so that \(|\Delta \mathcal{F}|=2st\) and then \(2st\le v-1\) considering that e cannot be covered by \(\Delta \mathcal{F}\). Thus the size of a \((G,\Gamma ,1)\) difference packing cannot exceed \(\lfloor {v-1\over 2s}\rfloor \). We say that \(\mathcal F\) is optimal when its size reaches this bound or, equivalently, when its leave has size at most equal to 2s. If \(\mathcal F\) has size exactly equal to \({v-1\over 2s}\) we say that it is perfect. In this case, it is also called a \((G,\Gamma ,1)\)difference family (see, e.g., [16]). Finally, when the difference leave L is a subgroup of G one says that \(\mathcal F\) is a relative \((G,L,\Gamma ,1)\) difference family.
Starting from a \((G,\Gamma ,1)\) difference packing with suitable properties it is possible to get a \((K_v,\Gamma )\)- or \((K_{v+1},\Gamma )\)- design in several ways.
Proposition 3.1
Let G be a group of order v and let \(\mathcal F\) be a \((G,\Gamma ,1)\) difference packing with difference leave L of size \(\ell \). Starting from \(\mathcal F\) one can obtain a \((K_v,\Gamma )\)-design in each of the following cases.
(i)
\(\mathcal F\) is perfect.
(ii)
There exists a \(\Gamma \)-decomposition of \(Cay[G:L\setminus \{e\}]\).
(iii)
L is a subgroup of G and there exists a \((K_{\ell },\Gamma )\)-design.
Also, one can obtain a \((K_{v+1},\Gamma )\)-design in each of the following cases.
(iv)
There exists a \(\Gamma \)-decomposition of \(Cay[G^+:L\setminus \{e\}]\).
(v)
L is a subgroup of G and there exists a \((K_{\ell +1},\Gamma )\)-design.
Proof
The assumption guarantees the existence of a G-regular \(\Gamma \)-decomposition \(\mathcal D\) of \(Cay[G:\Delta \mathcal{F}]\).
(i). Here we have \(\Delta \mathcal{F}=G\setminus \{e\}\) and then the assertion follows since \(Cay[G:G\setminus \{e\}]\) is nothing but the complete graph on G.
(ii). The blocks of \(\mathcal D\) and the blocks of a \(\Gamma \)-decomposition of \(Cay[G:L\setminus \{e\}]\) form a \(\Gamma \)-decomposition of \(Cay[G:\Delta \mathcal{F} \ \cup \ (L{\setminus }\{e\})]\) which is again the complete graph on G since \(\Delta \mathcal{F} \ \cup \ (L\setminus \{e\})=G\setminus \{e\}\) by definition of L.
(iii). In this case \(Cay[G:\Delta \mathcal{F}]=Cay[G:G\setminus L]\) is the complete equipartite graph whose parts are the right cosets of L in G. Given that a \((K_{\ell },\Gamma )\)-design exists by assumption, we can construct such a design with vertex \(L\star g\) for each coset \(L\star g\) of L in G. The blocks of \(\mathcal D\) together with the blocks of all these designs will give a \((K_v,\Gamma )\)-design.
(iv). The blocks of \(\mathcal D\) and the blocks of a G-regular \(\Gamma \)-decomposition of \(Cay[G^+:L\setminus \{e\}]\) form a G-regular \(\Gamma \)-decomposition of \(Cay[G^+:G\setminus \{e\}]\) which is the complete graph on \(G \ \cup \ \{\infty \}\), i.e., a complete graph of order \(v+1\).
(v). As in case (iii), \(Cay[G:\Delta \mathcal{F}]\) is the complete equipartite graph whose parts are the right cosets of L in G. Given that a \((K_{\ell +1},\Gamma )\)-design exists by assumption, we can construct such a design with vertex \(L\star g \ \cup \ \{\infty \}\) for each coset \(L\star g\) of L in G. The blocks of \(\mathcal D\) together with the blocks of all these designs will give a \((K_{v+1},\Gamma )\)-design. \(\square \)
We give a few easy examples illustrating the five cases of Proposition 3.1.
Consider the set \(\mathcal{F}=\{B_1,B_2\}\) consisting of the following two copies of \(P_6\) with vertices in the group of integers \(\mathbb {Z}\):
We have \(\Delta B_1=\pm \{1,2,3,4,5\}\) and \(\Delta B_2=\pm \{6,7,8,9,10\}\) so that we have \(\Delta \mathcal{F}=\pm \{1,2,3,4,5,6,7,8,9,10\}\). It is then evident that \(\mathcal{F}\) can be seen as a \((\mathbb {Z}_v,P_6,1)\) difference packing for every \(v\ge 21\). It is perfect for \(v=21\) and optimal (but not perfect) for \(22\le v\le 30\). The difference leave in the case \(v=26\) is \(L=\pm \{11,12\} \ \cup \ \{0,13\}\) and we see that the \(\mathbb {Z}_{26}\)-orbit of the path \(B_3=[0,11,-1,12,-2,13]\) is a \(P_6\)-decomposition of \(Cay[\mathbb {Z}_{26}:L\setminus \{0\}]\).
Thus \(\mathcal{F}\) is a set of base blocks for a cyclic \((K_{21},\Gamma )\)-design and \(\mathcal{F} \ \cup \ \{B_3\}\) is a set of base blocks for a cyclic \((K_{26},P_6)\)-design.
Now consider \(\mathcal F\) as a \((\mathbb {Z}_{29},P_6,1)\) difference packing. In this case the difference leave is \(L=\pm \{11,12,13,14\}\) and we see that the \(\mathbb {Z}_{29}\)-orbit of the path \(B_4=[\infty ,0,11,-1,12,-2]\) is a \(P_6\)-decomposition of \(Cay[\mathbb {Z}_{29}^+:L\setminus \{0\}]\). Thus \(\mathcal{F} \ \cup \ \{B_4\}\) is a set of base blocks for a 1-rotational \((K_{30},P_6)\)-design.
Consider the set \(\mathcal{F}=\{B_1,B_2\}\) consisting of the following two copies of \(M_4\) with vertices in \(\mathbb {Z}_{12}\):
We have \(\Delta B_1=\pm \{1,2\}\) and \(\Delta B_2=\pm \{4,5\}\) so that we have \(\Delta \mathcal{F}=\mathbb {Z}_{12}\setminus L\) with \(L=\{0,3,6,9\}\) the subgroup of \(\mathbb {Z}_{12}\) of order 4, i.e., \(\mathcal{F}\) is a relative \((\mathbb {Z}_{12},L,M_4,1)\) difference family. Thus \(\mathcal{B}=\{B_i+g \ | \ i=1,2; 0\le g\le 11\}\) is a \(M_4\)-decomposition of the complete tripartite graph whose parts are L, \(L+1\) and \(L+2\). Now note that the three copies of \(M_4\) below
form a L-regular \((K_4,M_4)\)-design. We conclude that \(\mathcal{D}=\mathcal{B} \ \cup \{A_i+j \ | \ i=1,2,3; j=0,1,2\}\) is a cyclic \((K_{12},M_4)\)-design.
Consider the copy of \(M_4\) with vertices in \(\mathbb {Z}_5\) given by \(C=[0,1] \ [2,4]\) and note that the singleton \(\{C\}\) is a \((\mathbb {Z}_5,M_4,1)\)-difference family so that a \((K_5,M_4)\)-design exists. Take again the decomposition \(\mathcal B\) of the tripartite graph with parts L, \(L+1\), \(L+2\) considered in the above paragraph. This time we construct a \((K_5,M_4)\)-design \(\mathcal{C}_i\) with vertex set \((L+i) \ \cup \ \{\infty \}\) for \(i=0,1,2\). Then \(\mathcal{B} \ \cup \ \mathcal{C}_0 \ \cup \ \mathcal{C}_1 \ \cup \ \mathcal{C}_2\) is a \((K_{13},M_4)\)-design.
4 Some strictly additive graph decompositions
We recall that the exponent of a group G, denoted exp(G), is the least common multiple of the orders of all elements of G. Observe that we have:
Fact 4.1
If B is a zero-sum k-subset of an abelian group G with exp(G) a divisor of k, then all the translates of B are zero-sum as well.
Proof
The sum \(\sigma _g\) of all elements of \(B+g\) is clearly \((\sum _{x\in B}x)+kg\). We have \(\sum _{x\in B}x=0\) since B is zero-sum, and \(kg=0\) since o(g) divides exp(G) which, in turn, divides k by assumption. Thus \(\sigma _g=0\) for every \(g\in G\). \(\square \)
As a consequence, we can state the following.
Remark 4.2
If exp(G) is a divisor of the order of \(\Gamma \), then a G-regular \((K_v,\Gamma )\)-design is strictly G-additive if and only if its base blocks are all zero-sum.
This remark allows to obtain a few infinite classes of strictly additive designs almost for free since they are implicitly present in the literature.
Theorem 4.3
Let \(q=p^n\) with p a prime. We have:
(1)
if \(q\equiv 1\) (mod kp) with \(k\in \{2,3,4\}\), then there exists a strictly EA(q)-additive \((K_q,C_{kp})\)-design;
(2)
if \(q\equiv 1\) (mod 6), then there exists a strictly EA(q)-additive \((K_q,\Gamma )\)-design for any generalized Petersen graph \(\Gamma \) of order 2p.
Proof
Studying EA(q)-regular \((K_q,C_k)\)-designs, Benini and Pasotti [3] proved, in particular, that whenever p, q and k are as in (1), there exists a \(\mathbb {F}_q\)-regular \((K_q,C_{kp})\)-design. Examining the proof of this result (Proposition 3.3 in [3]) one can check that all the base blocks of this design are zero-sum.
Also, studying EA(q)-regular \((K_q,\Gamma )\)-designs with \(\Gamma \) a generalized Petersen graph, Bonisoli et al. [6] established, in particular, that whenever p, \(\Gamma \) and q are as in (2), there exists an EA(q)-regular \((K_q,\Gamma )\)-design. A careful analysis of the proof of their result (Theorem 3.2 in [6]) shows that all the base blocks of this design are zero-sum.
Given that the exponent of EA(q) is p, the assertions follow from Fact 4.1. \(\square \)
In [13] we gave a construction method leading to infinitely many strictly additive 2-(v, k, 1) designs, namely additive \((K_v,K_k)\)-designs, whenever k is neither singly even nor of the form \(2^n3\). This result is interesting from a theoretical point of view but not practical since, apart from the case that k is a prime power, the values of v are huge in comparison with k. Here, by means of a similar method we are able to construct an infinite class of strictly additive \((K_v,C_k)\)-designs also for “small”values of v.
Following [7], we denote by \(\mathbb {F}_m\), for any \(m>1\), the ring that is the direct product of all the fields whose orders are the maximal prime powers dividing m. Thus, for instance, \(\mathbb {F}_{45} = \mathbb {F}_5 \times \mathbb {F}_9\). We will prove the following.
Theorem 4.4
If \(k>3\) is odd and every prime factor of m is also a factor of k, then there exists a strictly G-additive \((K_{mk}, C_k)\)-design with G the additive group of \(\mathbb {Z}_k\times \mathbb {F}_m\).
Proof
First note that exp(G) is a divisor of k.
Given that k is odd, it is obvious that m is odd as well, say \(m=2t+1\). Let Y be a complete system of representatives for the patterned starter of \(\mathbb {F}_m\). This means that Y is a t-subset of \(\mathbb {F}_m\setminus \{0\}\) such that \(\bigcup _{y\in Y}\{y,-y\}=\mathbb {F}_m{\setminus }\{0\}\). Let us distinguish two cases according to whether we have \(k\equiv 1\) or 3 (mod 4).
1st case: \(k\equiv 1\) (mod 4), say \(k=4n+1\).
Let \(\sigma =(\sigma _0,\sigma _1,\dots ,\sigma _{4n})\) be the zero-sum k-tuple of elements of \(\mathbb {Z}_k\) obtained by concatenating the single term (0), the 2n-sequence \((1,-1,2,-2,\dots ,n,-n)\), and its reverse \((-n,n,\dots ,-2,2,-1,1)\):
It is readily seen that the differences of the “oblique”edges through (0, 0) are \(\pm (1,y), \pm (1,-y)\), and that the differences of the “vertical”edge are \(\pm (0,2y)\). Also, the differences of the “horizontal”edges in the upper part of the cycle are, from left to right, \(\pm (2,-2y)\), \(\pm (3,-2y)\),...,\(\pm (2n,-2y)\). Correspondingly, the differences of the “horizontal”edges in the lower part are \(\pm (2,2y)\), \(\pm (3,2y)\),...,\(\pm (2n,2y)\). In summary, considering that \(\mathbb {Z}_k\setminus \{0\}=\pm \{1,2,\dots ,2n\}\), we have
which means that \(\mathcal F\) is a \((G,C_k,1)\) difference packing with difference leave \(L=\mathbb {Z}_k\times \{0\}\), i.e., a relative \((G,L,C_k,1)\) difference family. Thus the set \(\mathcal B\) of all the translates of the blocks of \(\mathcal F\) form a \(C_k\)-decomposition of the complete m-partite graph whose parts are the cosets of L in G, i.e., all sets \(L+(0,y)\) with \(y\in \mathbb {F}_m\). Now recall that a \((K_k,C_k)\)-design exists for every odd k. Hence, for each \(y\in \mathbb {F}_m\), we can take a set \(\mathcal{A}_y\) of k-cycles forming a \((K_k,C_k)\)-design with vertex-set \(L+(0,y)\). It follows that \(\mathcal{D}:=\mathcal{B} \ \cup \ \bigcup _{y\in Y}\mathcal{A}_y\) is a \((K_{mk},C_k)\)-design. We want to prove that \(\mathcal D\) is strictly G-additive, i.e., that all its blocks are zero-sum in G.
First note that each member \(B_y\in \mathcal{F}\) is zero-sum so that all blocks of \(\mathcal{B}\) are also zero-sum by Fact 4.1. Now note that L is zero-sum since it is a group of odd order. Then \(L+(0,y)\), that is the vertex set of every block of \(\mathcal{A}_y\), is zero-sum as well for every \(y\in \mathbb {F}_m\) by Fact 4.1 again. The assertion follows.
2nd case: \(k\equiv 3\) (mod 4), say \(k=4n-1\).
Let \(\sigma =(\sigma _0,\sigma _1,\dots ,\sigma _{4n-2})\) be the zero-sum k-tuple of elements of \(\mathbb {Z}_k\) obtained by concatenating the single term (2n), the \((2n-1)\)-sequence
For each \(y\in Y\), consider the k-cycle \(B_y=((\sigma _0,\tau _0),(\sigma _1,\tau _1),\dots ,(\sigma _{4n-2},\tau _{4n-2}))\) with vertices in G where the \(\tau _i\)’s are defined as in the first case. So this time we have:
Now the differences of the “oblique”edges are \(\pm (2n-1,y), \pm (2n-1,-y)\), whereas the differences of the “vertical”edge are still \(\pm (0,2y)\). The differences of the “horizontal”edges in the upper part of the cycle are, from left to right, \(\pm (2,-2y)\), \(\pm (3,-2y)\),...,\(\pm (2n-2,-2y)\) and finally \(\pm (1,2y)\). Correspondingly, the differences of the “horizontal”edges in the lower part are \(\pm (2,2y)\), \(\pm (3,2y)\),...,\(\pm (2n-2,2y)\) and finally \(\pm (1,-2y)\). In summary, considering that \(\mathbb {Z}_k\setminus \{0\}=\pm \{1,2,\dots ,2n-1\}\) we see that formulas (1) and (2) still hold and then, reasoning as in the first case, we will see that the assertion is true also in this case. \(\square \)
The above theorem gives, in particular, an additive \((K_{45},C_{15})\)-design. On the other hand, the smallest v for which a non-trivial additive \((K_v,K_{15})\)-design (a 2-(v, 15, 1) block design) is known is \(v=3\cdot 5^{31}\) (see [13]).
5 An additive strategy
Speaking of a ring R, it will be tacitly understood that it is commutative with unity. Also, saying that a design is R-additive we will mean that it is G-additive with G the additive group of R. A set of graphs \(\mathcal F\) with vertices in R will be said “zero-sum”if the vertices of any of its members sum up to zero in R.
For some graphs \(\Gamma \) as for instance the paths, finding direct constructions for additive \((K_v,\Gamma )\) designs using the methods of Sect. 4 does not appear to be easy. For these graphs we have to devise another technique which consists in looking for R-additive designs which are U-regular or \(U^+\)-rotational with U a suitable group of units of a ring R. We recall from Sect. 3.1 that in this setting the zero element of R takes on the role of the element \(\infty \) so that \(U^+=U \ \cup \ \{0\}\).
Theorem 5.1
Let \(\mathcal D\) be a U-regular or \(U^+\)-rotational \((K_v,\Gamma )\)-design with U a group of units of a ring R, and let \(\mathcal{F}\) be a set of base blocks for \(\mathcal D\). Then \(\mathcal D\) is R-additive if and only if \(\mathcal F\) is zero-sum.
Proof
Set \(\mathcal{F}=\{B_1,\dots ,B_n\}\) and let \(s_i\) be the sum of all vertices of \(B_i\). A block B of \(\mathcal D\) is of the form \(B=B_i\cdot u\) for some pair \((i,u)\in \{1,\dots ,n\}\times U\). The sum of all vertices of B is equal to \(s_i\cdot u\), therefore this sum is null if and only if \(s_i=0\). The assertion follows. \(\square \)
In particular, we have the following.
Theorem 5.2
Let U be a group of units of a ring R and let \(\mathcal F\) be a zero-sum \((U,\Gamma ,1)\) difference family. Then the \((K_v,\Gamma )\)-design generated by \(\mathcal F\) is R-additive.
We note that the idea of Theorem 5.1 is very similar to that used in [17] to construct Heffter spaces, that are resolvable partial linear spaces whose points form a complete system of representatives for the patterned starter of an abelian group G, and whose lines are all zero-sum in G.
The easiest way of applying Theorem 5.1 is to use it with \(R=\mathbb {F}_q\) for a suitable prime power q. In the following example we want to show an application where R is not a finite field.
Example 5.3
Let \(R=\mathbb {Z}_{33}\), let U be the group of units of R, so that we have
and let \(\mathcal{D}_i\) be the U-orbit of \(B_i\) for \(0\le i\le 4\). It is readily seen that \(\mathcal F\) is zero-sum. Note that \(B_0\) and \(B_1\) have trivial U-stabilizer whereas the U-stabilizers of \(B_2\), \(B_3\), \(B_4\) are \(\{1,10\}\), \(\{1,23\}\), and \(\{1,32\}\) (the three subgroups of U of order 2), respectively. Since the “differences”are “quotients”, we have \(\Delta B_0=\{25,4,7,19,2,17\}\), hence the singleton \(\{B_0\}\) is a \((U,M_6,1)\) difference packing whose leave L can be partitioned as
Note that \(\mathcal{D}_1\) is a \(M_6\)-decomposition of \(Cay[U^+:L_1]\). Also, for \(i=2,3,4\), \(\mathcal{D}_i\) is a \(M_6\)-decomposition of \(Cay[U:L_i]\). We conclude that \(\mathcal{F}\) is a zero-sum set of base blocks for a \(U^+\)-rotational \((K_{21},M_6)\)-design. Then \(\mathcal{D}=\bigcup _{i=0}^4\mathcal{D}_i\) is a \(\mathbb {Z}_{33}\)-additive \((K_{21},M_6)\)-design.
5.1 Looking for additive \((K_v,P_4)\)-designs
It is well-known that the trivial necessary conditions for the existence of a \((K_v,P_k)\)-design are also sufficient [33]. On the other hand, it does not seem easy to obtain general existence results for additive \((K_v,P_k)\)-designs, although we were able to construct many examples. For instance, a \((K_v,P_4)\)-design exists if and only if \(v\equiv 0\) or 1 (mod 3). By way of illustration, we present here a detailed recipe for constructing an additive \((K_v,P_4)\)-design with v admissible using Theorem 5.1 with R a finite field.
Case 1: \(v\equiv 0\) (mod 6).
Take a prime power \(q\equiv 1\) (mod \(v-1\)) and take \(V(K_v)=U^+\) with U the subgroup of \(\mathbb {F}_q^*\) of order \(v-1\);
find a zero-sum optimal \((U,P_4,1)\) difference packing \(\mathcal{F}\) and note that its leave L has size 5;
find a zero-sum 4-path \(B=[0,1,x,xy]\) where x, y are distinct elements of \(L\setminus \{1\}\) which are not inverse to each other.
Then \(\mathcal{F} \ \cup \ \{B\}\) is a zero-sum set of base blocks for an additive \((K_v,P_4)\)-design.
Case 2: \(v\equiv 1\) (mod 6).
Take a prime power \(q\equiv 1\) (mod v) and take \(V(K_v)=U\) with U the subgroup of \(\mathbb {F}_q^*\) of order v;
find a zero-sum \((U,P_4,1)\) difference family \(\mathcal{F}\).
Then \(\mathcal{F}\) is a zero-sum set of base blocks for an additive \((K_v,P_4)\)-design.
Case 3: \(v\equiv 3\) (mod 6).
Take a prime power \(q\equiv 1\) (mod \(v-1\)) and take \(V(K_v)=U^+\) with U the subgroup of \(\mathbb {F}_q^*\) of order \(v-1\);
find a zero-sum \((U,P_4,1)\) difference packing \(\mathcal{F}\) of size \(k-1\) if \(v=6k+3\), so that its leave L has size 8;
find a zero-sum 4-path \(A=[0,1,x,xy]\) with x, y distinct elements of \(L\setminus \{1,-1\}\) which are not inverse to each other;
consider the zero-sum path \(B=[1,z,-z,-1]\) with \(z\in L\setminus \{1,-1,x^{\pm 1},y^{\pm 1}\}\).
Then \(\mathcal{F} \ \cup \ \{A,B\}\) is a zero-sum set of base blocks for an additive \((K_v,P_4)\)-design.
Case 4: \(v\equiv 4\) (mod 6).
Take a prime power \(q\equiv 1\) (mod v) and take \(V(K_v)=U\) with U the subgroup of \(\mathbb {F}_q^*\) of order v;
find a zero-sum optimal \((U,P_4,1)\) difference packing \(\mathcal F\) so that its leave is of the form \(L=\{1,-1,x,x^{-1}\}\), and consider the zero-sum 4-path \(A=[1,x,-x,-1]\).
Then \(\mathcal{F} \ \cup \ \{A\}\) is a zero-sum set of base blocks for an additive \((K_v,P_4)\)-design.
The following table was obtained using the recipe presented above. The set of vertices will be \(U_n\) or \(U_n^+\) with \(U_n\) the subgroup of order n of \(\mathbb {F}_q^*\).
Our strategy fails in determining an additive \((K_v,P_4)\)-design for \(v\in \{18,19,21\}\). Here are the base blocks of a \(\mathbb {Z}_{173}\)-additive \((K_{43},P_4)\)-design:
Here, as an application of Theorem 5.1, we will be able to find an additive Steiner 2-design which, for the time being, appears to be sporadic. Indeed, as pointed out in the introduction, the known additive Steiner 2-designs are only the “geometric ones”, i.e., the point-line designs associated with an affine or projective geometry, and the cumbersome super-regular designs obtained in [13]. To find “handy” non-geometric examples appeared to be challenging.
Theorem 5.4
There exists an almost strictly \(\mathbb {F}_{5^3}\)-additive 2-(124, 4, 1) design.
Proof
Let us remind that a 2-(124, 4, 1) design is a \((K_{124},K_4)\)-design. Applying Theorem 5.1 with \(R=\mathbb {F}_{125}=\mathbb {Z}_5[x]/(x^3+3x+3)\) and \(U=\mathbb {F}_{125}^*\), it is enough to show that there exists a U-regular \((K_{124},K_4)\)-design whose base blocks are all zero-sum. We obtained this design with the aid of a computer.
Consider first the set \(\mathcal{F}=\{B_1,\dots ,B_{10}\}\) consisting of the following 4-subsets of U:
is the subgroup of order 4 of U. Thus \(\mathcal F\) is a relative \((G,L,K_4,1)\) difference family. The orbit of L, that is the set of cosets of L in U, is a \(K_4\)-decomposition of \(Cay[U:L\setminus \{1\}]\). We conclude that \(\mathcal{F} \ \cup \ \{L\}\) is a set of base blocks for a U-regular \((K_{124},K_4)\)-design.
Taking into account the basic identity \(x^3+3x+3=0\), one can check that all the blocks \(B_i\) are zero-sum (as usual, under addition). The block L is also zero-sum in view of Fact 2.2. The assertion then follows from Theorem 5.1. \(\square \)
6 Coseted designs
We introduce the following notion which will be useful to construct some infinite classes of additive designs.
Definition 6.1
A subset of \(\mathbb {Z}_n\) or \(\mathbb {Z}_n^+\) will be said coseted if it is partitionable into cosets of non-trivial subgroups of \(\mathbb {Z}_n\), and possibly \(\{\infty \}\). A \((K_v,\Gamma )\) design will be said coseted if we have \(V(K_v)=\mathbb {Z}_v\) or \(\mathbb {Z}_{v-1}^+\) and the vertex set of every block is coseted.
The following is obvious.
Proposition 6.2
A cyclic or 1-rotational \((K_v,\Gamma )\) design is coseted if and only if the vertex set of every base block is coseted.
It is possible to have coseted designs where some blocks are partitioned by cosets of at least two distinct subgroups of \(\mathbb {Z}_v\) (or \(\mathbb {Z}_{v-1}\)) and possibly \(\{\infty \}\). In the following example we present a cyclic design of order 30 with a base block partitioned by cosets of three distinct non-trivial subgroups of \(\mathbb {Z}_{30}\).
Example 6.3
The following copies of \(M_{10}\) with vertices in \(\mathbb {Z}_{30}\) are base blocks for a coseted \((K_{30},M_{10})\)-design.
Both the blocks \(B_1\) and \(B_2\) have trivial stabilizer whereas the blocks \(B_3\) and \(B_4\) have stabilizer \(\{0,6,12,18,24\}\) of order 5. Finally, the block \(B_5\) has stabilizer \(\{0,15\}\) of order 2. For \(i=1,\dots ,5\), the orbit \(\mathcal{D}_i\) of \(B_i\) is a \(M_{10}\)-decomposition of \(Cay[\mathbb {Z}_{30}:L_i]\) with the subsets \(L_i\) as follows:
Given that the \(L_i\)’s partition \(\mathbb {Z}_{30}\setminus \{0\}\), we have that \(\mathcal{D}:=\bigcup _{i=1}^5\mathcal{D}_i\) is a cyclic \(M_{10}\)-decomposition of \(Cay[\mathbb {Z}_{30}:\mathbb {Z}_{30}\setminus \{0\}]\), i.e., a \((K_{30},M_{10})\)-design. Let us check that its base blocks are coseted.
\(V(B_1)\)
is the union of the subgroup \(\{0,6,12,18,24\}\) of order 5, a coset \(\{1,16\}\) of the subgroup of order 2, and a coset \(\{9,19,29\}\) of the subgroup of order 3.
\(V(B_2)\)
is the union of five cosets of the subgroup of order 2, that are \(\{0,15\}\), \(\{1,16\}\), \(\{2,17\}\), \(\{5,20\}\), and \(\{7,22\}\).
\(V(B_3)\)
and \(V(B_4)\) are also union of two cosets of the subgroup of order 5 for the simple fact that \(B_3\) and \(B_4\) are stabilized by this subgroup.
Finally, the fact that \(B_5\) is stabilized by the subgroup of order 2 implies that \(V(B_5)\) is the union of five of its cosets.
Thus \(\mathcal D\) is a coseted design by Proposition 6.2.
Theorem 6.4
Every coseted design is additive.
Proof
Let \(\mathcal D\) be a coseted \((K_v,\Gamma )\)-design and distinguish two cases according to whether \(V(K_v)=\mathbb {Z}_v\) or \(\mathbb {Z}_{v-1}\).
1st case: \(V(K_v)=\mathbb {Z}_v\). Take any prime power \(q\equiv 1 \pmod {v}\) which certainly exists by Dirichlet’s theorem on arithmetic progressions (see, e.g., [32]). Now take a generator g of the subgroup G of \(\mathbb {F}_q^*\) of order v and consider the map
$$\begin{aligned} \phi : x\in \mathbb {Z}_v \longrightarrow g^x\in G. \end{aligned}$$
This map is bijective, hence it turns \(\mathcal D\) into an isomorphic \((K_v,\Gamma )\)-design \(\phi (\mathcal{D})\) where \(V(K_v)=G\) and where every block is of the form \(\phi (B)\) with B a coseted subset of \(\mathbb {Z}_v\). It follows that \(\phi (B)\) is partitioned by cosets of non-trivial subgroups of G since \(\phi \) is a group isomorphism. Hence \(\phi (B)\) is zero-sum in view of Fact 2.2. We conclude that \(\phi (\mathcal{D})\) is \(\mathbb {F}_q\)-additive.
2nd case: \(V(K_v)=\mathbb {Z}_v^+\). Take any prime power \(q\equiv 1 \pmod {v-1}\) which, again, exists by the theorem of Dirichlet. Now take a generator g of the subgroup G of \(\mathbb {F}_q^*\) of order \(v-1\) and consider the bijection \(\phi ^+: \mathbb {Z}_{v-1}^+ \longrightarrow G^+\) defined by \(\phi ^+(x)=g^x\) for every \(x\in \mathbb {Z}_{v-1}\), and \(\phi ^+(\infty )=0\). Considering that the restriction of \(\phi ^+\) to \(\mathbb {Z}_{v-1}\) is a group isomorphism and reasoning as in the first case, we see that \(\phi ^+\) turns \(\mathcal D\) into an isomorphic \((K_v,\Gamma )\)-design \(\phi ^+(\mathcal{D})\) where \(V(K_v)=G^+\) and where every block is partitioned by cosets of non-trivial subgroups of G and possibly \(\{0\}\), hence it is zero-sum in view of Fact 2.2. We conclude that \(\phi ^+(\mathcal{D})\) is \(\mathbb {F}_q\)-additive. \(\square \)
As an immediate consequence of the above theorem we have the following.
Corollary 6.5
If every base block of a cyclic or 1-rotational \((K_v,\Gamma )\)-design \(\mathcal{D}\) has non-trivial stabilizer, then \(\mathcal D\) is additive.
Proof
Take any base block B of \(\mathcal D\) and let S be its stabilizer. Then V(B) is also stabilized by S, hence V(B) is union of cosets of S and possibly \(\{\infty \}\) which means that B is coseted since S is not trivial by assumption. Thus \(\mathcal D\) is coseted by Proposition 6.2 and the assertion follows from Theorem 6.4. \(\square \)
This allows us to obtain one more infinite class of additive cycle-designs without any effort.
Theorem 6.6
There exists an additive \((K_v,C_k)\)-design for any admissible pair (v, k) with \(v<3k\) and k odd, k not a prime.
Proof
From a careful reading of the proof of Theorem 1.1 in [11] one deduces that for every pair (v, k) as in the statement there exists a 1-rotational \((K_v,C_k)\)-design with the property that no base cycle has trivial stabilizer. The assertion then follows from Corollary 6.5. \(\square \)
Example 6.7
The 1-rotational \((K_{21},C_{15})\)-design \(\mathcal D\) deducible from [11] has a set of base cycles \(\{A,B\}\) as follows:
Let us follow the instructions given in the proof of Theorem 6.4 in order to give an additive isomorphic copy of \(\mathcal D\). First, we have to consider a prime power \(q\equiv 1\) (mod 20); we take \(q=41\). Then we take \(g=2\) as generator of the subgroup G of \(\mathbb {F}_q^*\) of order 20, that is \(\mathbb {F}_{41}^\Box \). Now we have to consider the map \(\phi ^+:\mathbb {Z}_{20}^+ \longrightarrow G^+\) defined by \(\phi ^+(x)=2^x\) for every \(x\in \mathbb {Z}_{20}\) and \(\phi ^+(\infty )=0\). This map turns \(\mathcal D\) into the isomorphic \(G^+\)-rotational \((K_{21},C_{15})\)-design \(\phi ^+(\mathcal{D})\) where
is an isomorphic copy of \(\mathcal D\) whose blocks are all zero-sum in \(\mathbb {F}_{41}\).
Even though we are still not able to use Theorem 6.4 to get an infinite class of additive path-designs, combining the “coseted strategy”with some computer search it is possible to obtain several “promising”constructions as, for instance, the next one. In the following, any copy of \(K_5\setminus e\) (the complete graph \(K_5\) with one edge deleted) will be given by indicating the set of its vertices underlining the extremes of the deleted edge.
Theorem 6.8
Let \(v\equiv 5\) (mod 9) and suppose that there exists an optimal \((\mathbb {Z}_{2v},K_5\setminus e,1)\) difference packing where each base block is of the form \(\{\underline{0}, a,b,c, \underline{d}\}\) with \(d=v-c\). Then there exists an additive \((K_{2v},P_{10})\)-design.
Proof
Set \(v=9n+5\). Then an optimal \((K_{2v},K_5\setminus e,1)\) difference packing has size n, say \(\mathcal{F}=\{B_1,\dots ,B_n\}\). By assumption, for \(1\le i\le n\), there are suitable elements \(a_i, b_i, c_i\in \mathbb {Z}_v\) such that \(B_i=\{\underline{0},a_i,b_i,c_i,\underline{d_i}\}\) with \(d_i=v-c_i\). For each i, let us consider the 10-path
First note that each \(B'_i\) is coseted since \(V(B'_i)\) is partitioned by five cosets of \(\{0,v\}\) in \(\mathbb {Z}_{2v}\), that are \(\{0,v\}\), \(\{a_i,a_i+v\}\), \(\{b_i,b_i+v\}\), \(\{c_i,c_i+v\}\), \(\{d_i,d_i+v\}\). Then note that \(\Delta B_i=\Delta B'_i\) for every i so that \(\mathcal{F}':=\{B'_i \ | \ 1\le i\le n\}\) is an optimal \((\mathbb {Z}_{2v},P_{10},1)\) difference packing. Finally, note that the difference leave L of \(\mathcal{F}'\) has size 10 and necessarily contains 0 and v. Without loss of generality we can write \(L=\{\pm \ell _1,\pm \ell _2,\pm \ell _3,\pm \ell _4\} \ \cup \ \{0,v\}\) with \(1\le \ell _1<\ell _2<\ell _3<\ell _4<v\). Set \(\lambda _i=\sum _{j=1}^i(-1)^j\ell _j\), and consider the 10-path
It is readily seen that A is stabilized by \(\{0,v\}\). It is also easy to check that the orbit of A is a \(P_{10}\)-decomposition of \(Cay[\mathbb {Z}_{2v}:L\setminus \{0\}]\). Hence \(\mathcal{F} \ \cup \ \{A\}\) is a set of base blocks for a cyclic \((K_{2v},P_{10})\)-design. Given that these blocks are all coseted, we conclude that this design is additive by Proposition 6.2 and Theorem 6.4. \(\square \)
Applying the above theorem we get the following.
Proposition 6.9
There exists an additive \((K_{18n+10},P_{10})\)-design for \(1\le n\le 9\).
Proof
It is enough to exhibit an optimal \((K_{18n+10},K_5\setminus e,1)\) difference packing \(\mathcal F\) satisfying the special property required by Theorem 6.8 for \(1\le n\le 9\). These difference packings, obtained by computer search, are displayed in the table below.
The above seems to be a strong indication of the existence of a \((K_{18n+10},P_{10})\)-design for any n. On the other hand, finding a proof of such an existence result via Theorem 6.8 seems to be hard. Indeed the existence problem for an optimal \((K_{v},K_5\setminus e,1)\) difference packing is clearly much more difficult than the existence problem for an optimal \((K_{v},K_4,1)\) difference packing, which is equivalent to an optimal (v, 4, 1) optical orthogonal code. Now the second problem has been recently solved by Tao Feng et al. [35‐37] but that took more than 40 years!
Some strategies similar to that of Theorem 6.8 lead to many other examples of coseted \((K_v,P_k)\)-designs. On the other hand, for the time being, we do not have any infinite classes yet.
7 Two infinite classes of additive \((K_v, M_{2k})\)-designs
Recall that \(M_{2k}\) denotes the k-matching, i.e., the graph of order 2k consisting of k disjoint edges. The existence of \((K_{v},M_{2k})\)-designs for all admissible values of v, k (i.e., \(k\le v\) and \({v(v-1)\over k}\in \mathbb {Z}\)) is well known, see for instance [24]. Cyclic \((K_{v},M_{2k})\)-designs have also been studied: Hartman and Rosa [26] considered cyclic 1-factorizations (i.e., cyclic \((K_{2k},M_{2k})\)-designs) and proved that these exist if and only if 2v is not a power of 2 greater than 4, while Rees [29] proved the existence of a cyclic \((K_{v},M_{2k})\)-design for all other admissible values. More generally, the case of a \((K_{v},M_{2k})\)-design admitting a sharply vertex-transitive automorphism group was considered by Bonisoli and Bonvicini in [5].
Here we prove the existence of an additive cyclic \((K_v, M_{2k})\)-design with \(v\equiv 0\) (mod 2k) and \(1<k<{v\over 2}\), and also for \(v\equiv k+1\) (mod 2k) with \(k>1\) and \(v>k+1\).
Theorem 7.1
There exists an additive \((K_{2mk}, M_{2k})\) design for every pair (m, k) with \(k>1\).
Proof
The assertion is trivial for \(m=1\) (see Proposition 2.7). So, in the following, we will assume that \(m>1\).
Let \(G=\mathbb {Z}_{2mk}\) and let H be the subgroup of G of order k, hence \(H=\{2mi \ | \ 0\le i\le k-1\}\). Set \(X=\{1,2,\dots ,mk-1\} {\setminus } H\) and for each \(x\in X\), consider the k-matching \(A_x\) of the complete graph on G defined by
For every \(x\in X\) the G-stabilizer of \(A_x\) is clearly H and the G-orbit of \(A_x\) is a \(M_{2k}\)-decomposition of \(Cay[G:\{x,-x\}]\). Now distinguish two cases according to the parity of k.
is a k-matching of the complete graph on G whose G-stabilizer is \(\{0,mk\}\). Also, the G-orbit of B is a \(M_{2k}\)-decomposition of \(Cay[G:(H\setminus \{0\})\cup \{mk\}]\).
Considering that \(\bigcup _{x\in X}\{x,-x\} \ \cup \ (H{\setminus }\{0\}) \ \cup \ \{mk\}=G{\setminus }\{0\}\), we conclude that \(\{A_x \ | \ x\in X\} \ \cup \ \{B\}\) is a set of base blocks for a cyclic \((K_{2mk}, M_{2k})\)-design.
2nd case: k is even.
Consider the following k-matchings of the complete graph on G:
The stabilizers of \(B'\) and C are \(\{0,mk\}\) and \(\langle m\rangle \), respectively. Also, the orbits of \(B'\) and C are \(M_{2k}\)-decompositions of \(Cay[G:(H\setminus \{0,mk\})\cup \{2,-2\}]\) and \(Cay[G:\{mk\}]\), respectively.
Reasoning as in the first case, we can say that \(\{A_x \ | \ x\in X{\setminus }\{2\}\} \ \cup \ \{B',C\}\) is a set of base blocks for a cyclic \((K_{2mk}, M_{2k})\)-design.
Both in the first and second case all the base blocks have non-trivial stabilizer. The assertion follows from Corollary 6.5. \(\square \)
To prove the additivity of a \((K_{v}, M_{2k})\)-design with \(v\equiv k+1\) (mod 2k) and k odd is significantly less easy. From now on, given two integers a and b, we denote by [a, b] the set of all integers n with \(a\le n \le b\).
We shall use Skolem sequences: recall that a Skolem sequence of order n is a sequence \(S=(s_1,...,s_n)\) of n integers, such that
In the first case the sequence is said to be ordinary whereas it is said hooked in the second one. It is well-known that a Skolem sequence of order n exists for any value of n. For a survey on Skolem sequences, their variants, and their use in the construction of combinatorial designs, we refer to [23].
We also need the notion of a graceful or near-graceful cycle. We recall that a graph \(\Gamma \) of size s is graceful (or near-graceful) if there exists a copy B of \(\Gamma \) with vertices in [0, s] such that \(\Delta B=\pm [1,s]\) (or \(\pm [1,s+1]\setminus \{x\}\) for a suitable x). Such a B is said to be a graceful (or near-graceful) labeling of \(\Gamma \). If B is a near-graceful labeling, the element x of \([1,s+1]\setminus \Delta B\) is the “missing edge label”of B. We refer to [25] for a very rich survey on the huge literature on graceful graphs. We need the following.
Lemma 7.2
The k-cycle is graceful if and only if \(k\equiv 0\) or 3 (mod 4). Also, the k-cycle admits a near-graceful labeling with missing edge label k if and only if \(k\equiv 1\) or 2 (mod 4).
The first result is very well-known; it can be found in the seminal paper by Rosa [30], which started much of the research on graceful topics. The second result was given by Barrientos (see Theorem 1 in [2]).
We need another auxiliary lemma.
Lemma 7.3
Let \(2v=2mk+k+1\) with \(k\ge 3\) odd, and assume that there exists an optimal \((\mathbb {Z}_{2v},C_k,1)\) difference packing \(\mathcal{F}\) with the following properties:
(1)
B is vertex-disjoint with \(B+v\) for every \(B\in \mathcal{F}\);
(2)
if \(m=1\), that is to say \(\mathcal{F}=\{B_1\}\) is a singleton, then \(\Delta B_1=\pm [1,k]\) or \(\pm ([1,k+1]\setminus \{k\})\).
Then there exists an additive \((K_{2v}, M_{2k})\)-design.
Proof
Let \(\mathcal{F}=\{B_1,\dots ,B_m\}\) be an optimal difference packing as in the statement and let L be its leave. For each \(B_i=(b_{i,0}, b_{i,1}, \dots , b_{i,k-1})\in \mathcal{F}\) consider the set \(B'_i\) of edges of \(K_{2v}\) defined by
where it is understood that \(b_{i,k}=b_{i,0}\). Considering that \(B_i\) and \(B_i+v\) are vertex-disjoint by assumption, it is clear that \(B'_i\) is a k-matching of \(K_{2v}\). Note that we have \(\Delta B'_i=(\Delta B_i)+v\) and hence we see that \(\mathcal{F}'=\{B'_1,\dots ,B'_m\}\) is an optimal \((\mathbb {Z}_{2v},M_{2k},1)\) difference packing with difference leave \(L':=L+v\).
Assume first that \(m>1\) and set \(L'=\{\pm \ell _1,\dots ,\pm \ell _{(k-1)/2}\} \ \cup \ \{0,v\}\). Now construct, iteratively, a sequence \((x_1,\dots ,x_{(k-1)/2})\) of elements of \(\mathbb {Z}_{2v}\) as follows. Start taking \(x_1\) arbitrarily in \(\mathbb {Z}_{2v}\setminus \{0,v\}\) and then, once that \(x_{i-1}\) has been chosen, take \(x_{i}\) arbitrarily in the set
Note that this is possible since the “forbidden set" \(Y_i \ \cup \ (Y_i-\ell _i) \ \cup \ \{0,v\}\) has size at most equal to \(8(i-1)+2\le 8\cdot {k-3\over 2}+2<2v\) since we are assuming \(m>1\).
This choice of the elements \(x_i\) easily implies that the set of edges
is a k-matching of \(K_{2v}\). Note that its stabilizer is \(\{0,v\}\) and that its orbit is a \(M_{2k}\)-decomposition of \(Cay[\mathbb {Z}_{2v}:L'\setminus \{0\}]\). We conclude that \(\{B'_0,B'_1,\dots ,B'_m\}\) is a set of base blocks for a cyclic \((K_{2v}, M_{2k})\) design.
Now consider the case \(m=1\) so that \(\mathcal{F}=\{B_1\}\) and we have either \(\Delta B_1=\pm [1,k]\) or \(\Delta B_1=\pm ([1,k+1]{\setminus }\{k\}\).
If we have \(\Delta B_1=\pm [1,k]\), it is easy to see that we have \(L'=\pm [1,{k-1\over 2}]\). Let \(\sigma =(s_1,\dots ,s_{(k-1)/2})\) be a Skolem sequence of order \({k-1\over 2}\) and consider the set of edges
The fact that \(\sigma \) is a Skolem sequence guarantees that \(B'_0\) is a k-matching and then, reasoning as in the case \(m>1\), we deduce that \(\{B'_0,B'_1\}\) is a set of base blocks for a cyclic \((K_{2v}, M_{2k})\) design.
Now assume that we have \(\Delta B_1=\pm ([1,k+1]\setminus \{k\})\). In this case we can see that \(L'=\pm ([1,{k+1\over 2}]\setminus \{{k-1\over 2}\})\). Let \((s_1,\dots ,s_{(k+1)/2})\) be a Skolem sequence of order \({k+1\over 2}\) and consider the set of edges
Also here it is easy to deduce that \(\{B'_0,B'_1\}\) is a set of base blocks for a cyclic \((K_{2v}, M_{2k})\) design.
So, in every case, we have been able to construct a set \(\{B'_0,B'_1,\dots ,B'_m\}\) of base blocks for a cyclic \((K_{2v}, M_{2k})\) design. Observing that, in every case, all the blocks \(B'_i\) are coseted, we get the assertion from Proposition 6.2 and Theorem 6.4. \(\square \)
We are finally ready to prove one of the main results of this paper.
Theorem 7.4
There exists an additive \((K_{2v}, M_{2k})\)-design whenever \(2v=2mk+k+1\) with \(k\ge 3\) odd and \(m>0\).
Proof
For \(m=1\), by Lemma 7.3 it is enough to have a k-cycle \(B_1\) with vertices in \(\mathbb {Z}_{2v}\) such that \(B_1 \ \cap \ (B_1+v)\) is empty, and \(\Delta B_1\) is either \(\pm [1,k]\) or \(\pm ([1,k+1]\setminus \{k\})\). For \(k\equiv 3\) (mod 4) we can take a graceful labeling of \(C_k\) which exists by Lemma 7.2. For \(k\equiv 1\) (mod 4) we can take a near-graceful labeling of \(C_k\) with missing edge label k which, again, exists by Lemma 7.2.
Now assume that \(m>1\). By Lemma 7.3 it is enough to find an optimal \((\mathbb {Z}_{2v},C_k,1)\) difference packing \(\{B_1,\dots ,B_m\}\) in which each \(B_i\) is vertex-disjoint with \(B_i+v\). This can be done along the lines of the proof of Theorem 2.2 in [12] where, in particular, a perfect \((\mathbb {Z}_v,C_k,1)\) difference packing is essentially given for every pair (v, k) with \(v\equiv 1\) (mod 2k). Here, however, we have to be careful since we need the extra property that each block \(B_i\) has to be disjoint with its translate \(B_i+v\).
In each of the following cases \((s_1,\dots ,s_m)\) will denote a fixed Skolem sequence of order m.
Case 1: \(k=3\), hence \(2v=6m+4\).
For \(1\le i\le m\), take \(B_i=(0, -i, s_i+3m+2)\). The set of differences from the edges \(\{0,-i\}\) is \(\pm [1,m]\). Then, using (3), we see that the set of differences from the edges \(\{-i,s_i+3\,m+2\}\) and \(\{s_i+3\,m+2,0\}\) is \(\pm ([m+1,3m+1]\setminus \{\ell \})\) with \(\ell =m+1\) or \(m+2\). Thus \(\{B_1,\dots ,B_m\}\) is an optimal \((\mathbb {Z}_{2v},C_k,1)\) difference packing with leave \(L=\{0,\pm \ell , 3m+2\}\). The fact that \(B_i\) and \(B_i+v\) are vertex-disjoint for any i is pretty obvious.
Case 2: \(k=5\), hence \(2v=10m+6\).
For \(1\le i\le m\), take \(B_i=(0, \ s_i+i, \ i, \ -2\,m-1, \ i+3\,m+2)\). The differences from the edges \(\{0,s_i+i\}\) and \(\{s_i+i,i\}\) is \([1,2m+1]\setminus \{h\}\) with \(h=2m+1\) or 2m in view of (3). The list of differences from the edges \(\{i,-2m-1\}\) is \(\pm [2m+2,3m+1]\) whereas the list of differences from the edges \(\{-2m-1, i+3m+2\}\) is \(\pm [4m+3,5m+2]\). Finally, the list of differences from the edges \(\{i+3m+2,0\}\) is \(\pm [3m+3,4m+2]\). We conclude that \(\{B_1,\dots ,B_m\}\) is an optimal \((\mathbb {Z}_{2v},C_5,1)\) difference packing with difference leave \(L=\{0,\pm h,\pm (3m+2),5m+2\}\). Finally, it is easy to see that \(B_i\) and \(B_i+v\) are vertex-disjoint for any i.
Case 3: \(k\equiv 3\) (mod 4), \(k\ge 7\).
For \(1\le i\le m\), consider the k-cycle \(B_i=(b_{i,0},b_{i,1},\dots ,b_{i,k-1})\) with vertices in \(\mathbb {Z}_{2v}\) defined as follows.
With some patience, it is not difficult to check that \(\{B_1,\dots ,B_m\}\) is an optimal \((\mathbb {Z}_{2v},C_k,1)\) difference packing as required by Lemma 7.3 with difference leave \(L=\pm [mk+2,mk+{k-1\over 2}] \ \cup \ \{0,\pm \ell ,v\}\) with \(\ell =2k+1\) or 2k according to whether \((s_1,\dots ,s_m)\) is ordinary or hooked, respectively.
Case 4: \(k\equiv 1\) (mod 4), \(k\ge 9\).
For \(1\le i\le m\), let \(B_i=(b_{i,0},b_{i,1},\dots ,b_{i,k-1})\) be the k-cycle with vertices in \(\mathbb {Z}_{2v}\) defined as follows.
Also here, one can patiently check that \(\{B_1,\dots ,B_m\}\) is an optimal \((\mathbb {Z}_{2v},C_k,1)\) difference packing as required by Lemma 7.3. \(\square \)
Acknowledgements
We would like to express our gratitude to the referees for their comments and suggestions, which greatly improved this manuscript.
Declarations
Conflict of interest
The authors declare no conflict of interest.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Alspach B., Gavlas H.: Cycle decompositions of \(K_n\) and \(K_n-I\). J. Combin. Theory Ser. B 81, 77–99 (2001).MathSciNetCrossRef
2.
Barrientos C.: Graceful labelings of cyclic snakes. Ars Combin. 60, 85–96 (2001).MathSciNet
3.
Benini A., Pasotti A.: On the existence of elementary abelian cycle systems. Graphs Combin. 25, 1–14 (2009).MathSciNetCrossRef
4.
Beth T., Jungnickel D., Lenz H.: Design Theory. Cambridge University Press, Cambridge (1999).CrossRef
5.
Bonisoli A., Bonvicini S.: On the existence spectrum for sharply transitive \(G\)-designs, \(G\) a \([k]\)-matching. Discret. Math. 332, 60–68 (2014).MathSciNetCrossRef
6.
Bonisoli A., Buratti M., Rinaldi G.: Sharply transitive decompositions of complete graphs into generalized Petersen graphs, Innov. Incidence Geom. 6/7, 95–109 (2007/08)
7.
Bonvicini S., Buratti M., Garonzi M., Rinaldi G., Traetta T.: The first families of highly symmetric Kirkman triple systems whose orders fill a congruence class. Des. Codes Cryptogr. 89, 2725–2757 (2021).MathSciNetCrossRef
8.
Braun M., Etzion T., Östergård P.R.J., Vardy A., Wassermann A.: On the Existence of \(q\)-Analogs of Steiner Systems. Forum Math. Pi 4, e7 (2016).
9.
Bryant D., Colbourn C.J., Horsley D., Wanless I.M.: Steiner triple systems with high chromatic index. SIAM J. Discret. Math. 31, 2603–2611 (2017).MathSciNetCrossRef
10.
Bryant D., Horsley D.: A second infinite family of Steiner triple systems without almost parallel classes. J. Comb. Theory Ser. A 120, 1851–1854 (2013).MathSciNetCrossRef
11.
Buratti M.: Rotational \(k\)-cycle systems of order \(v < 3k\); another proof of the existence of odd cycle systems. J. Combin. Des. 11, 433–441 (2003).MathSciNetCrossRef
12.
Buratti M., Del Fra A.: Existence of cyclic \(k\)-cycle systems of the complete graph. Discret. Math. 261, 113–125 (2003).MathSciNetCrossRef
Francetić N., Mendelsohn E.: A survey of Skolem-type sequences and Rosa’s use of them. Math. Slovaca 59, 39–76 (2009).MathSciNetCrossRef
24.
Folkman J., Fulkerson D.R.: Edge colorings in bipartite graphs. In: Bose R.C., Dowling T. (eds.) Combinatorial Math. and Its Applications, pp. 561–577. Univ. N. Carolina Press, Chapel Hill (1969).
25.
Gallian J.A.: A dynamic survey on graph labeling. Electron. J. Combin. 6, 623 (2022).
26.
Hartman A., Rosa A.: Cyclic one-factorizations of the complete graph. Eur. J. Combin. 6, 45–48 (1985).MathSciNetCrossRef
27.
Keevash P.: The existence of designs. Preprint, arXiv:1401.3665.
28.
Pavone M.: A quasidouble of the affine plane of order \(4\) and the solution of a problem on additive designs. Finite Fields Appl. 92, 102277 (2023).MathSciNetCrossRef
29.
Rees R.: Cyclic \((0,1)\)-factorizations of the complete graph. J. Combin. Math. Combin. Comput. 4, 23–28 (1988).MathSciNet
30.
Rosa A.: On certain valuations of the vertices of a graph. In: Theory of Graphs (International Symposium, Rome, July 1966), pp. 349–355. Dunod Gordon & Breach Science Publishers Inc., New York (1967).
31.
Šajna M.: Cycle decompositions. III. Complete graphs and fixed length cycles. J. Combin. Des. 10, 27–78 (2002).MathSciNetCrossRef
32.
Serre J.-P.: A Course in Arithmetic. Springer, New York (1973).CrossRef
33.
Tarsi M.: Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs. J. Combin. Theory Ser. A 34, 60–70 (1983).MathSciNetCrossRef
34.
Wanless I.M., Webb B.S.: The existence of Latin squares without orthogonal mates. Des. Codes Cryptogr. 40, 131–135 (2006).MathSciNetCrossRef
35.
Zhang M., Feng T., Wang X.: The existence of cyclic \((v, 4, 1)\)-designs. Des. Codes Crypt. 90, 1611–1628 (2022).MathSciNetCrossRef
Zhao B., Zhao C., Chang Y., Feng T., Wang X., Zhang M.: Cyclic relative difference families with block size four and their applications. J. Combin. Theory Ser. A 206, 105890 (2024).MathSciNetCrossRef
