Down-linking (K
v, Γ)-designs to P
3-designs
A. Benini, L. Giuzzi and A. Pasotti∗
Abstract
Let Γ0 be a subgraph of a graph Γ. We define a down-link from a (Kv, Γ)-design B to a (Kn, Γ0)-design B0 as an injective map f : B → B0
mapping any block of B into one of its subgraphs. This is a new concept, closely related with both the classical notion of embedding and the more recent one of sampling. In the present paper we study down-links in general and prove that any (Kv, Γ)-design might be down-linked to a
(Kn, Γ0)-design, provided that n is suitably chosen. We also investigate
in detail down-links to P3-designs, P3 being the path with 3 vertices,
proving that it is always possible to take n ≤ v + 3. Furthermore, for several classes of graphs Γ, we provide explicit constructions of down-links from balanced Γ-designs to P3-designs, improving on the
aforementioned bound.
Keywords: down-link; embedding; (Kv, Γ)-design.
MSC(2010): 05B30, 05C38, 05C51.
1
Introduction
Let Kv be the complete undirected graph on v vertices, and assume Γ ≤ Kv
to be a subgraph of Kv. For any graph Γ, write V (Γ) for the set of vertices of
Γ and E(Γ) for the set of its edges. A (Kv, Γ)-design, also called a Γ-design of
order v, is a set B of graphs, called blocks, isomorphic to Γ and whose edges partition E(Kv). A (Kv, Γ)-design is balanced if each vertex of Kv occurs
in the same number of blocks. The problem of determining the existence of (Kv, Γ)-designs for a given graph Γ has been extensively studied; for surveys
on this topic see, for instance, [3, 4, 20]. We propose the following new definition.
Definition 1.1. Given a (Kv, Γ)-design B and a (Kn, Γ0)-design B0 with
Γ0 ≤ Γ, a down-link from B to B0 is an injective function f : B → B0 such that f (B) ≤ B, for any B ∈ B.
∗
anna.benini@ing.unibs.it, luca.giuzzi@ing.unibs.it, anita.pasotti@ing.unibs.it, Diparti-mento di Matematica, Facolt`a di Ingegneria, Universit`a degli Studi di Brescia, Via Valotti 9, I-25133 Brescia (IT).
If such a function f exists, that is if each block of B contains at least an element of B0 as a subgraph, we will say that it is possible to down-link B to B0.
In Section 2 we investigate the relationship between the new concept of down-link, the classical notion of embedding, see [21], and the recently defined concept of sampling, see [13]. In Section 3 we will introduce, in close analogy to embeddings, the main problems on the spectra of down-links and determine bounds on their minima. In Section 4 down-links from any (Kv, Γ)-design to P3-designs of order at most v + 3 are constructed; this
improves, for the case under consideration, on the values found in Section 3. In further sections 5, 6, 7, 8 we investigate the existence and construct down-links to P3-designs from, respectively, balanced star-designs, kite-designs,
cycle systems and path-designs; the problem of determining the spectrum of down-links to P3-designs is fully solved, by providing suitable functions, in
the case of stars and kites, as well as, for 4-cycle systems and P4-designs.
2
Down-linking, embedding and sampling
The notions of down-link, embedding and sampling are closely related. Recall that an embedding of a design B0 into a design B is a function ψ : B0 → B such that Γ ≤ ψ(Γ), for any Γ ∈ B0; see [21]. An injective embedding is called strict. Existence of embeddings of designs has been widely investigated. In particular, a great deal of interesting results are known on strict embeddings of path-designs; see, for instance, [8, 9, 10, 12, 16, 18, 19, 22, 23]. If ψ : B0 → B is a bijective embedding, clearly ψ−1 is a down-link from B to B0. The straightforward necessary condition for the existence of a bijective embedding of B0 into B, namely that B and B0 have the same number of blocks, is quite restrictive. However, as the following example shows, this does not necessarily lead to trivial embeddings.
Example 2.1. Consider the (K4, P3)-design
B0 = {Γ01 = [1, 2, 3], Γ02 = [1, 3, 0], Γ03= [2, 0, 1]}
and the balanced (K6, P6)-design
B = {Γ1 = [4, 0, 5, 1, 2, 3], Γ2 = [2, 5, 4, 1, 3, 0], Γ3 = [5, 3, 4, 2, 0, 1]}.
Define ψ : B0 → B by ψ(Γ0i) = Γi for i = 1, 2, 3. Then, ψ is a bijective
embedding; consequently, ψ−1 is a down-link from B to B0.
Obviously, a necessary condition for the existence of an embedding of a (Kn, Γ0)-design into a (Kv, Γ)-design is v ≥ n. On the contrary, the existence
of a down-link from a (Kv, Γ)-design to a (Kn, Γ0)-design implies neither
Example 2.2. Consider the balanced (K7, P4)-design
B = {[0, 3, 1, 2], [1, 0, 2, 3], [2, 6, 1, 4], [3, 6, 4, 5], [4, 3, 5, 6], [5, 2, 4, 0], [6, 0, 5, 1]},
and take the (K8, P3)-design
B0 = {[3, 1, 2], [0, 2, 3], [6, 1, 4], [6, 4, 5], [3, 5, 6], [2, 4, 0], [0, 5, 1], [7, 0, 3], [7, 1, 0], [7, 2, 6], [7, 3, 6], [7, 4, 3], [7, 5, 2], [7, 6, 0]}.
It is easy to see that B can be down-linked to B0. Clearly, as |B0| > |B|, an embedding of B0 into B cannot exist.
Down-links are also related to samplings. Samplings have been introduced in [13] for complete designs and studied extensively therein. In the case of graph decompositions, the analogous definition is the following.
Definition 2.3. Given a (Kv, Γ)-design B and a (Kn, Γ0)-design B0, with
Γ0 ≤ Γ, a sampling ξ is any surjective function ξ : B → B0 with ξ(B) ≤ B for all B ∈ B.
Indeed, both down-links and samplings act on elements of a design B in a similar way — namely, they map a graph Γ into one of its subgraphs, suitably chosen in B0. However, as the following Proposition 2.4 shows, any sampling, in the case of graph decompositions, is a bijective down-link and, as such, also the inverse of an embedding.
Proposition 2.4. Any sampling ξ of a (Kv, Γ)-design B into a (Kn, Γ0
)-design B0 is bijective.
Proof. By definition of sampling, ξ is surjective. For any e ∈ E(Kn), there
is exactly one graph Γ0 ∈ B0 with e ∈ E(Γ0). On the other hand, there is also exactly one graph Γ ∈ B with e ∈ E(Γ). It follows that the set of the preimages of Γ0 is {Γ}; hence, ξ is injective.
3
Spectrum problems
Let Γ0 ≤ Γ. The following spectrum problems about existence of embeddings have been considered.
(A) For each admissible n, determine the set S1(n) of all integers v such
that there exists some Γ0-design of order n embedded into a Γ-design of order v.
(B) For each admissible n, determine the set S2(n) of all integers v such that
For some classes of designs, problems (A) and (B) have been fully solved, respectively in [9, 12, 18, 22, 23] and [11, 12].
In the present paper we pose the following analogous questions about down-links:
(I) For each admissible v, determine the set L1(v) of all integers n such
that there exists some Γ-design of order v down-linked to a Γ0-design of order n.
(II) For each admissible v, determine the set L2(v) of all integers n such
that every Γ-design of order v can be down-linked to a Γ0-design of order n.
In general, write ηi(v; Γ, Γ0) = inf Li(v). When the graphs Γ and Γ0 are
easily understood from the context, we shall simply use ηi(v) instead of
ηi(v; Γ, Γ0).
The problem of the actual existence of down-links, for given Γ0 ≤ Γ, is addressed in Proposition 3.2. We recall the following lemma on the existence of finite embeddings for partial decompositions, a straightforward consequence of an asymptotic result by R.M. Wilson [28, Lemma 6.1]; see also [6].
Lemma 3.1. Any partial (Kv, Γ)-design can be embedded into a (Kn,
Γ)-design with n = O((v2/2)v2).
Proposition 3.2. For any v such that there exists a (Kv, Γ)-design and any
Γ0 ≤ Γ, the sets L1(v) and L2(v) are non-empty.
Proof. Fix first a (Kv, Γ)-design B. Denote by Kv(Γ0) the so called complete
(Kv, Γ0)-design, that is the set of all subgraphs of Kv isomorphic to Γ0, and
let ζ : B → Kv(Γ0) be any function such that ζ(Γ) ≤ Γ for all Γ ∈ B. Clearly,
the image of ζ is a partial (Kv, Γ0)-design P; see [7]. By Lemma 3.1, there is
an integer n such that P embeds into a (Kn, Γ0)-design B0. Let ψ : P → B0
be such an embedding; then, ξ = ψζ is, clearly, a down-link from B to a Γ0-design B0 of order n. Thus, we have shown that for any (Kv, Γ)-design
and for any Γ0≤ Γ the set L1(v) is non-empty.
To show that L2(v) is also non-empty, proceed as follows. Let ω be
the number of distinct (Kv, Γ)-designs Bi. For any i = 0, . . . , ω − 1, write
V (Bi) = {0, . . . , v − 1} + i · v. Consider now Ω =Sω−1i=0 Bi. Clearly, Ω is a
partial Γ-design of order vω. As above, take Kvω(Γ0) and construct a function
ζ : Ω → Kvω(Γ0) associating to each Γ ∈ Bi a ζ(Γ) ≤ Γ. The imageSiζ(Bi)
is a partial Γ0-design Ω0. Using Lemma 3.1 once more, we determine an integer n and an embedding ψ of Ω0 into a (Kn, Γ0)-design B0. For any i, let
ζi be the restriction of ζ to Bi. It is straightforward to see that ψζi : Bi→ B0
Notice that the order of magnitude of n is v2v2; yet, it will be shown that, in several cases, it is possible to construct down-links from (Kv, Γ)-designs
to (Kn, Γ0)-designs with n ≈ v.
Furthermore, it is easy to prove the following lower bound on η1(v; Γ, Γ0):
(v − 1) s
|E(Γ0)|
|E(Γ)| ≤ η1(v; Γ, Γ
0).
4
Down-linking (K
v, Γ)-designs to P
3-designs
In this section we shall focus our attention on the existence of down-links from (Kv, Γ)-designs to (Kn, P3)-designs. Observe first that it has been
shown in [26] that a (Kn, P3)-design exists if, and only if, n ≡ 0, 1(mod 4).
In order to prove our results we need some technical preliminaries. The star on k vertices Sk is the complete bipartite graph with one part having a
single vertex, say c, called the center of the star, and the other part having k − 1 vertices, say xi for i = 0, . . . , k − 2, called external vertices. In general,
we shall write Sk = [c; x0, x1, . . . , xk−2]. Consider the set
P3(Sk) = [x2`, c, x2`+1] | ` = 0, . . . , k − 3 2 . (1)
Note that if k is even, E(Sk) = E(P3(Sk)) ∪ {[c, xk−2]}, while if k is odd,
E(Sk) = E(P3(Sk)).
Let now B be a (Kv, Γ)-design with P3 ≤ Γ. For any B ∈ B, denote by P3(B)
a maximal partial decomposition of B in P3’s. Define also
R(B) = E(B) \ [
P ∈P3(B)
E(P ).
By the maximality of P3(B), distinct edges in R(B) have no vertex in
common. Write P3(B) = [ B∈B P3(B); R(B) = [ B∈B R(B).
Clearly, P3(B) is a partial, yet not necessarily maximal, (Kv, P3)-design.
If not all edges in R(B) are disjoint, extract as many P3’s from R(B) as
possible, thus determining a new set P3(R(B)). Let
R[(B) = {[x2i, x2i+1] | i = 0, . . . , µ − 1}
be the remaining disjoint edges and write V = V (Kv) \ V (R[(B)).
a) v ≡ 0(mod 4). In this case µ is even. Consider V (Kv+1) = V (Kv) ∪ {α}
and let Sα be the star with center α and external vertices the elements of V. Define Pα as
n
[x4i, x4i+1, α], [x4i, α, x4i+3], [α, x4i+2, x4i+3] | i = 0, . . . ,
jµ 2 k
− 1o
∪ P3(Sα). (2)
It is easy to see that
B0 = P3(B) ∪ P3(R(B)) ∪ Pα
is a (Kv+1, P3)-design.
b) v ≡ 1(mod 4). Also under this assumption µ is even. Write V (Kv+3) =
V (Kv) ∪ {α, β, γ}. Take Pα as in (2). Note that
P3(B) ∪ P3(R(B)) ∪ Pα
is a (Kv+1, P3)-design minus an edge, say e = [α, x]. Let Sβ and Sγ
respectively be the stars having center β and γ and external vertices V (Kv) \ {x}. Put
Pβ,γ= {[β, x, γ], [x, α, β], [α, γ, β]} ∪ P3(Sβ) ∪ P3(Sγ).
It might be easily verified that
B0= P3(B) ∪ P3(R(B)) ∪ Pα ∪ Pβ,γ
is a (Kv+3, P3)-design.
c) v ≡ 2(mod 4), which implies µ odd. Write V (Kv+2) = V (Kv) ∪ {α, β}
and take Pα as in (2). Let Sβ be the star with center β and external vertices the elements of V (Kv). Define
Pβ = {[x
2µ−2, x2µ−1, α], [x2µ−2, α, β]} ∪ P3(Sβ).
It is possible to directly check that
B0 = P3(B) ∪ P3(R(B)) ∪ Pα ∪ Pβ
is a (Kv+2, P3)-design.
d) v ≡ 3(mod 4), so µ is odd. Write V (Kv+1) = V (Kv) ∪ {α}. Take Sα and
Pα as in (2). Note that since Sα has an odd number of external vertices,
we have E(Sα) \ E(P3(Sα)) = [α, y]. Let
P = {[x2µ−2, x2µ−1, α], [x2µ−2, α, y]}.
It is not hard to verify that
B0 = P3(B) ∪ P3(R(B)) ∪ Pα ∪ P
Any f : B → B0 mapping B ∈ B to a B0 ∈ P3(B) is a down-link.
We may now state the main theorem of this section. Theorem 4.1. For any (Kv, Γ)-design with P3 ≤ Γ,
η1(v) ≤ η2(v) ≤ v + 3.
The down-links constructed above are not, in general, to designs whose order is as small as possible; thus, Theorem 4.1 does not provide, unless further assumptions are made, η1(v) exactly.
Remark 4.2. In general, a (Kn, P3)-design can be trivially embedded into P3
-designs of any admissible order m ≥ n. Thus, for down-links to P3-designs,
given any n ∈ Li(v),
{m ≥ n | m ≡ 0, 1(mod 4)} ⊆ Li(v) ⊆ {m ≥ ηi(v) | m ≡ 0, 1(mod 4)}.
Hence, solving problems (I) and (II) for (Kv, Γ)-designs is actually equivalent
to determining exactly the values η1(v; Γ, P3) and η2(v; Γ, P3).
5
Balanced star-designs
In this section the existence of down-links from balanced star-designs to P3-designs is investigated; in particular, we shall use the notations introduced
at the beginning of Section 4.
In [27], Tarsi proved that a (Kv, Sk)-design exists if, and only if, v ≥ 2k−2
and v(v −1) ≡ 0(mod 2k −2). It is not hard to verify that a balanced (Kv, Sk
)-design exists if, and only if, v > 1 and v ≡ 1(mod 2k − 2).
Suppose then v ≡ 1(mod 2k − 2), v > 1. Denote by LS1(v) the set of all the
integers n ≡ 0, 1(mod 4) such that there exists some balanced Sk-design of
order v down-linked to a P3-design of order n. Write LS2(v) for the set of
all the integers n ≡ 0, 1(mod 4) such that every balanced Sk-design of order
v can be down-linked to a P3-design of order n. We shall fully determine the
sets LS1(v) and LS2(v), solving problems (I) and (II).
Theorem 5.1. Assume k ≥ 3. For every v ≡ 1(mod 2k − 2), v > 1,
LS2(v) ⊆ LS1(v) ⊆ {n | n ≥ v, n ≡ 0, 1(mod 4)}.
Proof. Let B be a balanced (Kv, Sk)-design and let B0 be a (Kn, P3)-design.
A direct computation proves that any vertex of Kv is contained in exactly (v−1)k
2(k−1) blocks of B. Let x ∈ V (Kv). Write m for the number of blocks of B
whose center is x and p for the number of blocks of B where x is external, so that m + p = (v−1)k2(k−1). Since in Sk the center has degree k − 1, while an
Hence, any vertex of Kv is the center of 2(k−1)v−1 > 0 stars of B. Let now
f : B → B0 be a down-link. For every S ∈ B, f (S) contains the center of S. Hence, the image of B by f contains every vertex of Kv. Thus, n ≥ v.
Lemma 5.2. Assume v ≡ 1(mod 4) admissible. Then, every balanced (Kv, Sk)-design can be down-linked to a (Kv, P3)-design.
Proof. Let B be a balanced (Kv, Sk)-design. Note that k is odd, since
v ≡ 1(mod 4) and v ≡ 1(mod 2k − 2). It is easy to see that
B0 = [
Sk∈B
P3(Sk),
where P3(Sk) is as in (1), is a P3-design of order v. A function f : B → B0,
sending any Sk to a P3 ∈ P3(Sk), is a down-link.
Lemma 5.3. Assume v ≡ 3(mod 4) admissible. Then, every balanced (Kv, Sk)-design can be down-linked to a (Kv+1, P3)-design.
Proof. Let B be a balanced (Kv, Sk)-design. Note that, since v ≡ 3(mod 4),
k is even and every c ∈ V (Kv) is the center of an odd number of stars, say
m. Let V (Kv+1) = V (Kv) ∪ {α}. We can write B =Sc∈V Bc, where Bc is
the set of the stars of B with center c. For any c ∈ V (Kv) consider
P3(Bc) = {P3(Sk) | Sk ∈ Bc}.
Observe that the edges of Bc not contained in P3(Bc) give a star Sc∗ =
[c; y0, . . . , ym−1] of center c and with m edges. Define
Bc∗= {[α, c, ym−1]}.
It is easy to see that
B0 = [
c∈V
P3(Bc) ∪ P3(Sc∗) ∪ Bc∗
is a (Kv+1, P3)-design. Note that if m = 1, then P3(Sc∗) is empty for all c ∈ V .
Any function f : B → B0 mapping Sk to a P3∈ P3(Sk) is a down-link.
In general, provided the conditions hold, any given (Kv, Sk)-design B can
be down-linked to several non-equivalent (Kn, P3)-designs B0. Even if B0 is
fixed, the construction of a down-link f : B → B0 is not unique. Actually, it is easy to see that lemmas 5.2 and 5.3 do provide with bk−12 cv(v−1)2(k−1) distinct
Example 5.4. We apply the previous construction with v = 11 and k = 6. Let V (K11) = Z11. It can be directly verified that B = {St = [t; 1 + t, 2 +
t, 3 + t, 4 + t, 5 + t] | t ∈ Z11} is a balanced (K11, S6)-design. Any vertex of
K11 is the center of exactly one star of B; actually, in this case m = 1. Now
we construct the following sets of P3’s:
[ c∈Z11 P3(Bc) = { [1, 0, 2], [3, 0, 4], [2, 1, 3], [4, 1, 5], [3, 2, 4], [5, 2, 6], [4, 3, 5], [6, 3, 7], [5, 4, 6], [7, 4, 8], [6, 5, 7], [8, 5, 9], [7, 6, 8], [9, 6, 10], [8, 7, 9], [10, 7, 0], [9, 8, 10], [0, 8, 1], [10, 9, 0], [1, 9, 2], [0, 10, 1], [2, 10, 3] }; [ c∈Z11 P3(Sc∗) = ∅; [ c∈Z11 B∗c = { [α, 0, 5], [α, 1, 6], [α, 2, 7], [α, 3, 8], [α, 4, 9], [α, 5, 10], [α, 6, 0], [α, 7, 1], [α, 8, 2], [α, 9, 3], [α, 10, 4] }.
One can check that B0 = S
c∈Z11P3(Bc) ∪ B
∗
c is a (K12, P3)-design on the
vertex-set Z11∪ {α}. A down-link f acts, for instance, by mapping any
St∈ B to f (St) = [1 + t, t, 2 + t] ∈ B0.
Theorem 5.5. Let k ≥ 3. For every admissible v,
LS1(v) = LS2(v) = {n | n ≥ v, n ≡ 0, 1(mod 4)}.
Proof. The assertion follows directly from Theorem 5.1, Lemma 5.2, Lemma 5.3 and Remark 4.2.
6
Balanced kite-designs
Denote by D = [a, b, c ./ d] the kite, a triangle with an attached edge, having vertices {a, b, c, d} and edges [c, a], [c, b], [c, d], [a, b].
In [2], Bermond and Sch¨onheim proved that a kite-design of order v exists if, and only if, v ≡ 0, 1(mod 8). In particular, a balanced kite-design of order v exists if, and only if, v ≡ 1(mod 8); see [14].
Let v ≡ 1(mod 8), v > 1. Denote by LD1(v) the set of all the integers
n ≡ 0, 1(mod 4) such that there exists some balanced D-design of order v down-linked to a P3-design of order n. Denote by LD2(v) the set of all the
integers n ≡ 0, 1(mod 4) such that every balanced D-design of order v can be down-linked to a P3-design of order n. In this section we determine the
sets LD1(v) and LD2(v).
Theorem 6.1. For every v ≡ 1(mod 8), v > 1,
Proof. Let B be a balanced (Kv, D)-design and B0 a (Kn, P3)-design. Note
that, since B is balanced, the number b of blocks in which a vertex x ∈ V (Kv)
has degree 3 is the same as the number of blocks in which x has degree 1. By hypothesis, suppose there exists a down-link f : B → B0. Observe that for every D = [a, b, c ./ d] ∈ B, f (D) must contain c. Hence, V (Kn) contains
each vertex of V (Kv) having degree different from 2 in at least one block of
B. Let now x, y ∈ V (Kv) be two vertices having degree 2 in all the blocks of B in which they appear. Since B is a (Kv, D)-design, there must be a block
D = [x, y, c ./ d] ∈ B. Hence, f (D) contains either x or y. Thus, we can state that V (Kn) must contain all V (Kv), apart from, at most, one vertex,
having degree 2 in all the blocks in which it appears. It follows n ≥ v − 1. Lemma 6.2. Let v = 1(mod 8), v > 1. Every balanced (Kv, D)-design can
be down-linked to a (Kv, P3)-design.
Proof. Let B = {Dj = [aj, bj, cj ./ dj] | j = 1, . . . ,v(v−1)8 } be a balanced
(Kv, D)-design. It is immediate to see that
B0 = P0j = [aj, bj, cj], P1j = [aj, cj, dj] | j = 1, . . . , v(v − 1) 8
is a (Kv, P3)-design and that f : B → B0, mapping Dj into P0j, is a
down-link.
Lemma 6.3. Let v = 1(mod 8), v > 1. Suppose there exists a balanced (Kv, D)-design B having a vertex x ∈ V (Kv) with degree 2 in all the blocks
in which it appears. Then, B can be down-linked to a (Kv−1, P3)-design.
Proof. Let B be a balanced (Kv, D)-design satisfying the hypothesis in the
statement. By the choice of x, we can write
B = Dix= [x, yi, zi./ ti] | i = 1, . . . , v − 1 2 ∪ Dj = [aj, bj, cj ./ dj] | j = 1, . . . , (v − 4)(v − 1) 8 . Now consider B0 = Pi= [yi, zi, ti] | i = 1, . . . , v − 1 2 ∪ P0j = [aj, bj, cj], P1j = [aj, cj, dj] | j = 1, . . . , (v − 4)(v − 1) 8 .
It is easy to see that B0 is a P3-design of order v − 1 whose vertex-set is
V (Kv) \ {x}. Let now f : B → B0, mapping Dj into P0j for any j =
1, . . . ,(v−4)(v−1)8 , and mapping Dix into Pi for any i = 1, . . . ,v−12 . The
Theorem 6.4. For every v ≡ 1(mod 8), v > 1,
LD2(v) = {n | n ≥ v, n ≡ 0, 1(mod 4)}.
If there exists a (Kv, D)-design satisfying the hypothesis of Lemma 6.3 then
LD1(v) = {n | n ≥ v − 1, n ≡ 0, 1(mod 4)};
otherwise,
LD1(v) = {n | n ≥ v, n ≡ 0, 1(mod 4)}.
Proof. The theorem follows from Theorem 6.1, Lemma 6.2, Lemma 6.3 and Remark 4.2.
Example 6.5. We provide an application of Lemma 6.3 with v = 9. One can check that
B = {[2, 3, 1 ./ 4], [6, 9, 1 ./ 5], [2, 9, 7 ./ 1], [3, 7, 8 ./ 1], [8, 9, 4 ./ 2], [6, 8, 2 ./ 5], [3, 6, 4 ./ 7], [3, 9, 5 ./ 4], [6, 7, 5 ./ 8]}
is a balanced (K9, D)-design with three vertices, 3, 6, 9, having degree 2 in all
the blocks in which they appear. So we are able to down-link B to a P3-design
of order 8. Choose, for instance, V (K8) = V (K9) \ {9}. We have
B0 = {[2, 3, 1], [2, 1, 4], [6, 1, 5], [2, 7, 1], [3, 7, 8], [3, 8, 1], [8, 4, 2], [6, 8, 2], [6, 2, 5], [3, 6, 4], [3, 4, 7], [3, 5, 4], [6, 7, 5], [6, 5, 8]}.
It is easy to see that B can be down-linked to B0.
Example 6.6. In this example we consider a balanced (K9, D)-design B not
satisfying the hypothesis of Lemma 6.3; thus, it is not possible to down-link B to a P3-design whose vertex-set is smaller than V (K9). We construct a
down-link from B to a P3-design of order 9. Let
B = {[0, 1, 4 ./ 6], [1, 2, 5 ./ 7], [2, 3, 6 ./ 8], [3, 4, 7 ./ 0], [4, 5, 8 ./ 1], [5, 6, 0 ./ 2], [6, 7, 1 ./ 3], [7, 8, 2 ./ 4], [8, 0, 3 ./ 5]}.
Following the construction of Lemma 6.2,
B0= {[0, 1, 4], [0, 4, 6], [1, 2, 5], [1, 5, 7], [2, 3, 6], [2, 6, 8], [3, 4, 7], [3, 7, 0], [4, 5, 8], [4, 8, 1], [5, 6, 0], [5, 0, 2], [6, 7, 1], [6, 1, 3], [7, 8, 2], [7, 2, 4], [8, 0, 3], [8, 3, 5]}.
7
Cycle systems
Let Ck be the cycle on k vertices. It is well known that there exists a k-cycle
system of order v, namely a (Kv, Ck)-design, if, and only if, k 6 v, v is
odd and v(v − 1) ≡ 0 (mod 2k). The if part of this theorem was solved by Alspach and Gavlas [1] for k odd (see [5] for a simpler proof) and by ˜Sajna [24] and [25] for k even.
Let now v ≥ k be odd and v(v − 1) ≡ 0 (mod 2k). Denote by LCk1(v) the set of all the integers n ≡ 0, 1(mod 4) such that there exists some Ck-design
of order v down-linked to a P3-design of order n. Write LCk2(v) for the set of
all the integers n ≡ 0, 1(mod 4) such that every Ck-design of order v can be
down-linked to a P3-design of order n.
For any cycle Ck= (c0, c1, . . . , ck−1) ∈ B, define
P3(Ck) = [c2`, c2`+1, c2`+2] | ` = 0, . . . , k − 2 2 , (3)
where the indexes are taken mod k. Note that if k is odd, E(Ck) =
E(P3(Ck)) ∪ [ck−1, c0]; if k is even, E(Ck) = E(P3(Ck)), instead. Observe
also that, for k even, the graph Ckx obtained from Ck by removing a vertex
x ∈ Ck is a path on k − 1 vertices and, consequently, has an even number of
edges. Given a path P2h+1 = [a0, a1, . . . , a2h] with an even number of edges,
let
P3(P2h+1) = {[a2`, a2`+1, a2`+2] | ` = 0, . . . , h − 1} . (4)
Obviously, E(P2h+1) = E(P3(P2h+1)). Also, for a path with an odd number
of edges, say P2h= [a0, a1, . . . , a2h−1], let
P3(P2h) = {[a2`+1, a2`+2, a2`+3] | ` = 0, . . . , h − 2} . (5)
Note that E(P2h) = E(P3(P2h)) ∪ [a0, a1].
Theorem 7.1. Suppose k even. For any admissible v, {n | n ≥ v − 1, n ≡ 0, 1(mod 4)} ⊆ LCk
2(v) ⊆ LCk1(v).
Proof. Take a (Kv, Ck)-design B and fix a vertex x ∈ Kv. Write B = B1∪ B2,
where
B1= {Ck ∈ B : x 6∈ Ck},
B2= {Ck ∈ B : x ∈ Ck}.
We want to down-link B to a (Kv−1, P3)-design. Thus, construct the set
B0 = {P3(Ck) | Ck∈ B1} ∪ {P3(Ckx) | Ck∈ B2}.
Since B is a design, B0 is a (Kv−1, P3)-design with vertex-set V (Kv) \ {x}.
It is easy to see that f : B → B0, mapping any cycle Ck∈ B1 to an element
of P3(Ck) and any cycle Ck ∈ B2 to an element of P3(Ckx), is a down-link.
Theorem 7.2. Suppose v ≡ 1 (mod 8), v > 1. Then,
LC42(v) = LC41(v) = {n | n ≥ v − 1, n ≡ 0, 1(mod 4)}.
Proof. We have only to prove that LC41(v) ⊆ {n | n ≥ v −1, n ≡ 0, 1(mod 4)}. Let B be a (Kv, C4)-design and let B0 be a (Kn, P3)-design. Suppose f :
B → B0 to be a down-link. For every C ∈ B, its image f (C) contains 3 of its vertices. Since B is a design, any two vertices of V (Kv) are contained
together in at least one block of B. It easily follows that V (Kn) contains all
the vertices of V (Kv) apart from, at most, one.
The case of k-cycle systems with k odd requires some further preliminaries. we recall some well known results about matchings of graphs; for further references, see [17]. A matching M in a graph Γ is a set of edges of Γ, no two of which are incident. A maximum matching is a matching that contains the largest possible number of edges. For any graph Γ and any set X ⊆ V (Γ), write ∆(X) for the set of all vertices of Γ adjacent to at least one vertex of X. We recall Philip Hall’s Theorem on matchings for bipartite graphs. Theorem 7.3 (P. Hall). Let Γ = A ∪ B be a bipartite graph. Then, Γ has a matching of A into B if, and only if, |∆(X)| ≥ |X|, for any X ⊆ A.
The matching of Theorem 7.3 has |A| edges and, thus, is maximum. Lemma 7.4. Suppose k odd and let v ≡ 1(mod 4) be admissible. Any (Kv, Ck)-design can be down-linked to a (Kv, P3)-design.
Proof. Let B be a (Kv, Ck)-design, and take V (Kv) = {0, 1, . . . , v − 1} ⊆ Z.
Write B =Sv−k
i=0 Bi, where
Bi = {C ∈ B | min V (C) = i}.
We can assume without loss of generality c0 = i for any C ∈ Bi. We want to
deal first with the sets Bi for i ≥ 1. If |Bi| is even, let P3(Bi) = {P3(C) | C ∈
Bi} and note that E(Bi) \ E(P3(Bi)) is a star Si of center i and with an
even number of external vertices. For any i where |Bi| is odd, fix a Ci ∈ Bi.
Observe that |Bi\ {Ci}| is even, so it is possible to construct a set of P3’s
as above from Bi\ {Ci}. Write C for the set of all Ci’s extracted from Bi’s
with |Bi| odd. Clearly, |C| ≤ v − k.
Introduce the graph G with V (G) = C and [Ci, Cj] ∈ E(G) if, and only if, V (Ci) ∩ V (Cj) 6= ∅; let M be one of its maximum matchings. For any edge [Ci, Cj] of M, write the cycles Ci and Cj in such a way as to have c0∈ V (Ci) ∩ V (Cj) and define
P3(Ci, Cj) = P3(Ci) ∪ P3(Cj) ∪ [cik−1, c0, cjk−1]. (6)
Let now D = C \ V (M). This set is possibly empty. In any case D is a set of cycles which are pairwise disjoint; hence, |D| ≤ bv−1k c. Since v ≡ 1(mod 4),
both |D| and |B0| are even. Construct now the bipartite graph G0= D ∪ B0,
where [D, B] ∈ E(G0) if, and only if, V (D) ∩ V (B) 6= ∅. It is not hard to verify that G0 satisfies the hypotheses of P. Hall’s Theorem 7.3 and |D| ≤ |B0|; thus, G0 has a maximum matching M0 covering all the vertices
of D. For any [D, B] ∈ M0, construct the set P3(D, B) as in (6). Consider
now D0 = B0 \ (B0∩ V (M0)). Since |D| is even, |D0| is also even. We
can write D0 = {D0, . . . , D2m−1} and, for any ` = 0, . . . , m − 1, construct
P3(D2`, D2`+1) as in (6). The union of all the P3’s obtained as above, that
is the set B0 = v−k [ i=1 P3(Bi) \ [ C∈C P3(C) ! ∪ v−k [ i=1 P3(Si) ∪ [ [X,Y ]∈ E(M)∪E(M0) P3(X, Y ) ∪ m−1 [ `=0 P3(D2`, D2`+1) , (7)
is a (Kv, P3)-design. Any map f : B → B0 sending B ∈ B to P3 ∈ P3(B) is
clearly a down-link.
Lemma 7.5. Suppose k odd and let v ≡ 3(mod 4) be admissible. Any (Kv, Ck)-design can be down-linked to a (Kv+1, P3)-design.
Proof. Proceed as in the proof of Lemma 7.4. Since v ≡ 3(mod 4), the number |D0| is odd. Thus, at the end of the construction, there remain to
arrange the edges of a cycle D2m= (0, d1, . . . , dk−1) ∈ D0. Write V (Kv) =
{0, . . . , v − 1} and V (Kv+1) = V (Kv) ∪ {α} and consider
P = P3(D2m) ∪ P3(Sα) ∪ {[dk−1, 0, α]},
where Sα is the star of center α and external vertices {1, . . . , v − 1}. The set B0 of (7) in the proof of Lemma 7.4 together P gives a (Kv+1, P3)-design.
The result follows as usual.
Theorem 7.6. Take k odd. For any admissible v,
{n | n ≥ v, n ≡ 0, 1(mod 4)} ⊆ LC2k+12 (v) ⊆ LC2k+11 (v).
Proof. The theorem follows directly from Lemma 7.4, Lemma 7.5 and Remark 4.2.
8
Balanced path-designs
In this section we investigate down-links from balanced path-designs to P3-designs. Problems (I) and (II) are also completely solved for k = 4.
Tarsi [26] proved that the necessary conditions for the existence of a (Kv, Pk)-design, namely v ≥ k and v(v − 1) ≡ 0(mod 2(k − 1)), are also
sufficient. In [15], Hung and Mendelsohn proved that a balanced (Kv, P2k+1
)-design (k ≥ 1) exists if, and only if, v ≡ 1(mod 4k), and that a balanced (Kv, P2k)-design (k ≥ 2) exists if, and only if, v ≡ 1(mod 2k − 1). Balanced
path-designs are also known as handcuffed designs; see [15].
For each admissible v, denote by LPk1(v) the set of all the integers n ≡ 0, 1(mod 4) such that there exists some balanced Pk-design of order v
down-linked to a P3-design of order n. Write LPk2(v) for the set of all the
integers n ≡ 0, 1(mod 4) such that every balanced Pk-design of order v can
be down-linked to a P3-design of order n.
We shall extensively use the notation (4) for paths, as introduced in Section 7.
Theorem 8.1. Let v ≡ 1(mod 2k − 1), with v, k > 1.
{n | n ≥ v, n ≡ 0, 1(mod 4)} ⊆ LP2k2 (v) ⊆ LP2k1 (v).
Proof. Let B be a balanced (Kv, P2k)-design. It is always possible, for any
path P and vertex a ∈ P to remove an edge [a, b] from P so that each of the remaining connected components Pa+ and Pa− contains an even number of edges. For any two paths P, Q ∈ B with a ∈ V (P ) ∩ V (Q) 6= ∅, consider the components Pa+, Pa−, Qa+, Qa− and let [a, b] and [a, c] be respectively the edge removed from P and that removed from Q. Define
P3(P, Q) = P3(Pa+) ∪ P3(Pa−) ∪ P3(Qa+) ∪ P3(Qa−) ∪ {[c, a, b]}. (8)
Write V (Kv) = {0, 1, . . . , v − 1} ⊆ Z and let
Bi= { B ∈ B | min V (B) = i };
it is immediate to see that |B0| = (v−1)k2k−1 and B =Sv−2ki=0 Bi. For i > 0, fix a
maximal set Ci of disjoint pairs of Bi and construct, for any of these pairs,
P3’s as in (8), thus determining partial decompositions P3(Ci). Let now C
be the set of all paths in Bi with i > 0 not in any of the elements of Ci.
Clearly, |C| ≤ v − 2k. Proceed as in Lemma 7.4, using (8) instead of (6) and, determine D = C \ V (M). It is immediate to see that |D| ≤ v−1
2k .
Construct, as in the aforementioned lemma the graph G0 and determine a maximum matching M0 and the set D0 = B0 \ (B0∩ V (M0)). Let C0
be a maximal set of disjoint pairs of elements of D0. There are now two
possibilities:
1. v ≡ 0, 1(mod 4); in this case |B| also |D0| are even and C0 covers all
the elements of D0. Thus, we obtain a (Kv, P3)-design B0 given by
B0 = v−2k [ i=0 P3(Ci) ∪ [ [X,Y ]∈ E(M)∪E(M0) P3(X, Y ). (9)
2. v ≡ 2, 3(mod 4); in this case |B| is odd, as well as |D0|. In particular,
there is a path P ∈ D0 not covered by C0. Let [0, p] be the edge of P
neither in P0+ nor in P0−.
If v ≡ 2(mod 4), we construct a (Kv+2, P3)-design B0. Write V (Kv+2) =
V (Kv)∪{α, β} and denote by Sαand Sβrespectively the stars of center
α and β and external vertices {1, 2, . . . , v − 2}. Take then
B0 = v−2k [ i=0 P3(Ci) ∪ [ [X,Y ]∈ E(M)∪E(M0) P3(X, Y ) ∪ P3(P0+) ∪ P3(P0−) ∪ P3(Sα) ∪ P3(Sβ) ∪ {[α, 0, p], [α, v − 1, β], [0, β, α]}. (10)
If v ≡ 3(mod 4) we construct a (Kv+1, P3)-design B0 as follows. Let
V (Kv+1) = V (Kv) ∪ {α} and define B0 = v−2k [ i=0 P3(Ci) ∪ [ [X,Y ]∈ E(M)∪E(M0) P3(X, Y ) ∪ P3(P0+) ∪ P3(P0−) ∪ P3(Sα) ∪ {[α, 0, p]}, (11)
where Sα is the star with center α and external vertices {1, . . . , v − 1}. It is easy to see that in all of the above cases there is a down-link f : B → B0. The main result follows from Remark 4.2.
Example 8.2. Consider the (K16, P4)-design B whose blocks are given by
the union of the sets
B0 ={[0, 4, 15, 11], [0, 10, 5, 11], [0, 15, 10, 3], [0, 1, 3, 4], [0, 7, 12, 13], [12, 0, 2, 5], [9, 0, 8, 11], [3, 0, 5, 8], [6, 0, 11, 7], [13, 0, 14, 10]}; B1 ={[1, 8, 6, 7], [1, 5, 7, 8], [1, 14, 12, 8], [1, 4, 9, 15], [1, 11, 13, 14], [2, 1, 12, 15], [7, 1, 6, 15], [13, 1, 9, 5], [10, 1, 15, 8]}; B2 ={[2, 9, 14, 7], [2, 12, 10, 6], [2, 15, 7, 3], [2, 6, 4, 10], [3, 2, 4, 5], [14, 2, 10, 11], [8, 2, 7, 13], [11, 2, 13, 10]}; B3 ={[3, 13, 8, 14], [15, 3, 14, 4], [9, 3, 5, 6], [6, 3, 8, 9], [12, 3, 11, 14]}; B4 ={[4, 11, 9, 10], [4, 8, 10, 7], [4, 7, 9, 12], [13, 4, 12, 5]}; B5 ={[5, 15, 13, 6], [14, 5, 13, 9]}; B6 ={[9, 6, 11, 12], [12, 6, 14, 15]}.
Here only B1 and B3 contain an odd number of blocks. Observe that Bi= ∅
for i > 6. We may apply the construction of Theorem 8.1. Consider, for instance the set B3. In this case
and, consequently
P3(C3) = {[13, 8, 14], [3, 14, 4], [13, 3, 15], [3, 5, 6], [3, 8, 9], [9, 3, 6]}
Hence [12, 3, 11, 14] ∈ D. An analogous argument for B1 gives
D = {[10, 1, 15, 8], [12, 3, 11, 14]}. A matching M0 is given by
M0= {([12, 3, 11, 14], [0, 4, 15, 11]), ([10, 1, 15, 8], [0, 10, 5, 11])} and |C0| = 8. We may now construct a (K16, P3)-design, according to (9).
Example 8.3. Consider the balanced (K6, P6)-design
B = {[0, 5, 1, 4, 2, 3], [1, 0, 2, 5, 3, 4], [5, 4, 0, 3, 1, 2]}. In this case B = B0. We have
P3([0, 5, 1, 4, 2, 3], [1, 0, 2, 5, 3, 4]) = {[5, 1, 4], [4, 2, 3], [0, 2, 5], [5, 3, 4], [5, 0, 1]}. Let P = [5, 4, 0, 3, 1, 2]; thus, P0− = [5, 4, 0]; P0+= [3, 1, 2]. Then, B0= {[5, 1, 4], [4, 2, 3], [0, 2, 5], [5, 3, 4], [5, 0, 1], [5, 4, 0], [3, 1, 2]} ∪ {[1, α, 2], [3, α, 4]} ∪ {[1, β, 2], [3, β, 4]} ∪ {[α, 0, 3], [α, 5, β], [0, β, α]}.
Note that, in this case, Theorem 8.1 does not provide a down-link from B to a design with the minimum number of vertices; indeed, B can also be down-linked to the (K5, P3)-design
B00= {[5, 1, 4], [4, 2, 3], [5, 3, 4], [3, 1, 2], [2, 5, 4]}. Theorem 8.4. Let v ≡ 1(mod 3), v > 1
LP42(v) = LP41(v) = {n | n ≥ v, n ≡ 0, 1(mod 4)}.
Proof. By Theorem 8.1, it remains only to prove that LP41(v) ⊆ {n | n ≥ v, n ≡ 0, 1(mod 4)}. Let B be a balanced (Kv, P4)-design and B0 a (Kn, P3
)-design. Suppose a down-link f : B → B0 exists. For any P = [a, b, c, d] ∈ B, f (P ) contains the internal vertices of B. On the other hand, since B is balanced, each vertex is contained in 2(v−1)3 blocks and, in particular, it is internal in exactly v−13 > 0 of these. Hence, n ≥ v follows.
Theorem 8.5. Let v ≡ 1(mod 4k) with v > 1,
{n ≥ v | n ≡ 0, 1(mod 4)} ⊆ LP2k+12 ⊆ LP2k+11
Proof. It is sufficient to observe that every P2k+1 can be decomposed into k
References
[1] Alspach B., Gavlas, H., Cycle decompositions of Kn and Kn− I, J.
Combin. Theory Ser. B 81 (2001), 77–99.
[2] Bermond, J.C., Sch¨onheim, J., G-decomposition of Kn, where G has
four vertices or less, Discrete Math. 19 (1977), 113–120.
[3] Bos´ak, J., “Decompositions of graphs”, Mathematics and its Applica-tions (1990), Kluwer Academic Publishers Group.
[4] Bryant, D., El-Zanati, S., Graph Decompositions, CRC Handbook of Combinatorial Designs, C.J. Colbourn and J.H. Dinitz, CRC Press (2006), 477–486.
[5] Buratti, M., Rotational k-cycle systems of order v < 3h; another proof of the existence of odd cycle systems, J. Combin. Designs 11 (2003), 433–441.
[6] Buratti, M., Pasotti, A., Combinatorial designs and the theorem of Weil on multiplicative character sums, Finite Fields Appl. 15 (2009), 332-344.
[7] Colbourn, C. J., Hamm, R. C., Lindner C. C., Rodger A., Embedding partial graph designs, block designs, and triple systems with λ > 1, Canad. Math. Bull. 29 (1986), 385–391.
[8] Colbourn, C. J., Ling, A. C. H., Quattrocchi, G., Minimum embedding of P3-designs into (K4−e)-designs, J. Combin. Des. 11 (2003), 352–366.
[9] Colbourn, C. J., Ling, A. C. H., Quattrocchi, G., Embedding path designs into kite systems, Discrete Math. 297 (2005), 38–48.
[10] Colbourn, C. J., Ling, A. C. H., Quattrocchi, G., Embedding path designs into D-designs, where D is a triangle with an attached edge, preprint.
[11] Doyen, J., Wilson R.M., Embeddings of Steiner triple systems, Discrete Math. 297 (2005), 38–48.
[12] Gionfriddo, M., Quattrocchi, G., Embedding balanced P3-designs into
(balanced) P4-designs, Discrete Math. 308 (2008), 155–160.
[13] Giuzzi, L., Pasotti, A., Sampling complete designs, preprint (arXiv:0907.3199)
[14] Huang, C., Balanced graph designs in small graphs, Utilitas Math. 10 (1976), 77-108.
[15] Hung, S.H.Y., Mendelsohn N.S., Handcuffed designs, Aequationes Math. 18 (1974), 256–266.
[16] K¨uc¨ukcifci, S., Lindner, C., Quattrocchi, G., Embeddings of P3-designs
into bowtie and almost bowtie systems, Discrete Math. 309 (2009), 5675–5677.
[17] Lov´asz L., Plummer, M.D., “Matching Theory”, Annals of Discrete Mathematics 29 (1986).
[18] Milici, S., Quattrocchi, G., Embedding handcuffed designs with block size 2 or 3 in 4-cycle systems, Combinatorics (Assisi, 1996). Discrete Math. 208/209 (1999), 443–449
[19] Milici, S., Minimum embedding of P3-designs into TS(v, λ), Discrete
Math. 308 (2008), 331–338.
[20] Pasotti, A., “Graph Decompositions with a sharply vertex transitive automorphism group”, Ph.D. Thesis, Universit`a degli Studi di Milano Bicocca (2006).
[21] Quattrocchi, G., Embedding G1-designs into G2-designs, a short survey,
Rend. Sem. Mat. Messina Ser. II 8 (2001), 129–143.
[22] Quattrocchi, G., Embedding path designs in 4-cycle systems, Combina-torics ’98 (Palermo). Discrete Math. 255 (2002), 349–356.
[23] Quattrocchi, G., Embedding handcuffed designs in D-designs, where D is the triangle with attached edge, Discrete Math. 261 (2003), 413–434.
[24] ˜Sajna, M., Cycle decompositions of Kn and Kn− I, Ph.D. Thesis,
Simon Fraser University, July 1999.
[25] ˜Sajna, M., Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Designs 10 (2002), 27–78.
[26] Tarsi, M., Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs, J. Combin. Theory Ser. A 34 (1983), 60–70.
[27] Tarsi, M., Decomposition of complete multigraphs into stars, Discrete Math. 26 (1979), 273–278.
[28] Wilson, R.M., Construction and uses of pairwise balanced designs, Math. Centre Tracts 55 (1974), 18–41.
