Path Decompositions of the Kneser Graph
by
Thomas Whitt
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
May 5, 2013
Keywords: graph decompositions, Kneser graph, generalized Kneser graph, path
decompositions, graph embeddings
Copyright 2013 by Thomas Whitt
Approved by
Chris Rodger, Chair, Don Logan Endowed Chair of Mathematics and Associate Dean for
Research in the College of Sciences and Mathematics
Dean Ho man, Professor of Mathematics
Peter Johnson, Professor of Mathematics
Curt Lindner, Distinguished University Professor of Mathematics
Abstract
Necessary and su cient conditions are given for the existence of a graph decomposition
of the Kneser Graph KGn;2 into paths of length three and four, and of the Generalized
Kneser Graph GKGn;3;1 into paths of length three. A solution is also presented for the
problem of embedding maximal H-designs, where H is a path of length three.
ii
Acknowledgments
On a professional note, I would like to thank the Auburn University Department of
Mathematics and my committee for their numerous contributions to my success at the grad-
uate level. In particular, I would like to thank Dr. Chris Rodger for his outstanding patience
and commitment to excellence that led to this dissertation (hopefully) being of the highest
quality.
On a personal level, I would like to thank my family for their unwavering support and
con dence, as well as the FA crew. They know why.
iii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 History and Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 P3-decompositions of KGn;2 and GKGn;3;1 . . . . . . . . . . . . . . . . . . . . . 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 A P3-Decomposition of KGn;2 . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 A P3-Decomposition of GKGn;3;1 . . . . . . . . . . . . . . . . . . . . . . . . 16
3 P4-decompositions of KGn;2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Useful Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 A P4-Decomposition of KGn;2 . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Embedding Partial P3-systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3 Embedding Partial P3-designs. . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4 Further Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
iv
List of Figures
2.1 Partitioning the Vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 The Two H5?s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Example of the H4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1 The K8?s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 B0;1;j . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
v
Chapter 1
Introduction
1.1 De nitions
A graph G is an ordered pair (V;E) where V is a set of objects known as vertices and
E is a set of two element subsets of V called edges. The edge fu;vg is said to join the
vertices u and v. A complete graph of order n, denoted by Kn, is a graph with n vertices
in which each pair of vertices is joined by an edge. A bipartite graph is a graph G in which
the vertices of G can be partitioned into two parts M and N such that the edge set is a
subset of E = ffx;ygjx2M;y2Ng; so no edges join two vertices in the same part. If
the edge set of G equals E, then G is called a complete bipartite graph with parts M and N
and is denoted Km;n or K(M;N), where jMj= m and jNj= n. The star of order m is the
complete bipartite graph K1;m = Sm (for convenience, we allow the possibility that m = 0).
The vertex of Sm with degree m when m 2 is said to be the center of Sm; if m = 1 then
either vertex can be designated the center. A path of length n, Pn = (v0;v1;:::;vn), is a
sequence of n + 1 distinct vertices such that for 0  i < n, fvi;vi+1g is an edge in G. A
cycle of length n is the graph that can be formed from a path of length n 1 by joining the
 rst and last vertices. The join of two graphs G and H, denoted by G_H, is the graph
with vertex set V(G)[V(H) and edge set E(G)[E(H)[ffa;bgja2V(G);b2V(H)g.
A graph G0 = (V0;E0) is said to be a subgraph of G = (V;E) if V0 V, E0 E.
An H-decomposition of a graph G = (V;E) is a pair (V;B), where B is a collection of
edge-disjoint subgraphs of G, each isomorphic to H, whose edges partition E(G). If G is
chosen to be the complete graph on n vertices then an H-decomposition of G is also referred
to as an H-design of order n. A 3-cycle design of order n is often referred to as a Steiner Triple
System. An H-design of a subgraph of Kn is also referred to as a partial H-design of order
1
n. The leave of a partial H-design (V;P) of order n is the graph L = (V(Kn);E(Kn)nE(P))
where E(P) =feje2E(H);H2Pg. A partial H-design is said to be maximal if its leave
contains no subgraphs isomorphic to H.
The set of k element subsets of a set V is denoted Tk(V).
1.2 History and Context
Over the years, many di erent graph decomposition problems have been studied, using
various subgraphs for the decomposition. Perhaps the most common family of decomposi-
tions studied are cycle decompositions. One of the earliest graph theoretic problems was
posed by Kirkman [16] in 1847 which asks, for a given x, to  nd the largest subgraph of Kx
which has a 3-cycle decomposition.
In the 1960?s, a great deal of work was done in solving the problem of cycle designs. In
1965, K otzig found necessary and su cient conditions for 4k-cycle designs of order n where
n 1 (mod 8k) [18]. The next year, Rosa found p-cycle designs of order n where p 2
(mod 4) and n = 2kp+ 1 for any k and p [23]. The solution to the odd cycle decomposition
problem waited until 1989 when it was partially solved by Ho man, Rodger, and Lindner
[14] and then until 2001 where it was completely solved by Alspach and Gavlas [1].
G need not be limited to the complete graph. For instance, in 2001, Alspach and
Gavlas found necessary and su cient conditions for the existence even cycle decompositions
of K2m F, the complete graph of even order with the edges of a 1-factor F removed [1],
and in 2002,  Sajna settled the existence problem for odd cycle decompositions of K2m F
[24].
Another graph for which cycle decompositions have been widely studied is the complete
multipartite graph. One of the most prominent results for this problem was proved by
Sotteau in 1981 [26]. Sotteau showed that there exists a 2k-cycle decomposition of Km;n if
and only if m;n k, m and n are even, and 2kjmn. More recently, stemming from statistical
designs, G has been chosen to be the graph formed from a complete multipartite graph with
2
multiplicity  2 (i.e., each pair of vertices in di erent parts are joined by  2 edges) by adding
a copy of  1Kn to each part of size n (i.e., each pair of vertices in the same part are joined
by  1 edges) and H is a 3-cycle [10], a 4-cycle [11], or a Hamilton cycle [3].
Other types of graph decompositions have also been well studied in the literature. Of
particular interest related to this dissertation is the work of Michael Tarsi. In 1979, Tarsi
found necessary and su cient conditions for a decomposition of  Kn into stars of order m
[27]. In 1983, he completely solved the problem of decomposing  Kn into paths of length m
[28]. In this paper he showed that the obvious necessary conditions for an m-path decompo-
sition of  Kn, namely that mjjE( Kn)j and n m + 1, are also su cient. In Chapters 2
and 3 of this dissertation, companion results are obtained by  nding necessary and su cient
conditions for decomposing the Kneser and Generalized Kneser graphs into paths of length
three (See Theorems 2.1 and 2.2 respectively). In Chapter 4, necessary and su cient condi-
tions for decomposing the Kneser Graph into paths of length four are found (see Theorem
3.1).
The Kneser Graph KGn;k is de ned to be the graph whose vertices are the k-element
subsets of some set of n elements, in which two vertices are adjacent if and only if their
intersection is empty. The Generalized Kneser Graph, GKGn;k;r is de ned to be the graph
whose vertices are the k-element subsets of some set of n elements in which two vertices
are adjacent if and only if they intersect in precisely r elements. The graph-decomposition
problem of  nding necessary and su cient conditions for the existence of P3-decompositions
of KGn;2 and GKGn;3;1 is completely solved in Theorem 2.1 and 2.2 respectively, and the
problem of the existence of P4-decompositions of KGn;2 is completely solved in Theorem 3.1.
An explicit construction is provided to  nd the relevant decompositions.
It is worth noting that Kneser graphs have attracted much interest in the years since
Kneser  rst described them in 1955 [17]. In particular, this interest has centered on solving
the conjecture by Kneser that  (KGn;k) = n 2k + 2 whenever n 2k [17], where  (G)
is the chromatic number of G (KGn;k has no edges if n < 2k). The  rst proof of Kneser?s
3
conjecture was given by Lov asz in 1978. What makes Lov asz?s proof so interesting is that
it wasn?t of a combinatorial nature at all, but rather topological. Lov asz used the Borsuk-
Ulam theorem which states, in essence, that any continuous function from the n-sphere
into Euclidean n-space must map some pair of antipodal points to the same point. This
application of a theorem in a seemingly unrelated  eld to what was perceived as a purely
combinatorial problem was revelatory, and is considered one of the most in uential works
in the  eld of topological combinatorics. In the years after Lov asz?s proof, several other
proofs were published, but all of them were essentially topological in nature [4, 12]. A purely
combinatorial proof of Kneser?s conjecture wasn?t found until 2004, when Matou sek proved
the result using Tucker?s lemma which deals with vertex labellings in particular triangulations
[22].
Another problem regarding Kneser graphs that has received a good deal of attention
is to  nd the values of n and k for which KGn;k contains a Hamilton cycle. In 2000, Chen
showed that Kneser graphs are Hamiltonian if n 3k [8]. The current conjecture is that
all Kneser Graphs are Hamiltonian if n 2k + 1 with the exception of KG5;2 which is the
Petersen Graph. It has been shown computationally that all connected Kneser graphs with
n  27 except for the Petersen Graph are indeed Hamiltonian [25]. The veracity of this
conjecture in general is still an open problem.
In Chapter 4, the problem of embedding maximal partial 3-path designs is addressed.
The embedding problem can be thought of as follows: for each partial H-design (V0;P0) of
order n,  nd the set of integers M such that m2M if and only if there exists an H-design
(V;P) of Km such that V0 V and P0 P. This dissertation also completely solves the
problem of embedding maximal partial P3-designs.
Various embedding problems have been studied extensively in the literature as well.
Given the amount of study received by cycle decomposition problems over the years, it
is perhaps not surprising that partial cycle system embeddings are also among the most
studied embedding problems. In particular, the problem of partial Steiner Triple System
4
embeddings has been a major focus over the years and was only recently solved. In 1977,
Lindner conjectured that any partial Steiner Triple System of order u can be embedded in a
Steiner Triple System of order v if v 1;3 (mod 6) and v 2u+ 1 [20]. The next thirty-two
years saw steady progress made towards proving this conjecture. Lindner had already shown
in 1975 that any partial Steiner Triple System of order u can be embedded in a Steiner Triple
System of order 6u+ 3 [19]. In 1980, Anderson, Hilton and Mendelsohn improved the bound
to v 4u + 1 and v 1;3 (mod 6) [2]. The bound was improved again in 2004 by Bryant
to 3u 2 [6]. The conjecture was  nally proved in 2009 by Bryant and Horsley using a new
technique, dubbed \repacking" [7].
1.3 Techniques
In Chapters 2 and 3, where path decompositions of Kneser and Generalized Kneser
graphs are considered, the main technique utilized is taking advantage of the highly struc-
tured nature of the underlying graph. By cleverly partitioning the element set that generates
the vertices, predictable subgraphs can be induced by selecting vertices containing elements
in various parts of the partition. These subgraphs can be catalogued in a fairly straightfor-
ward manner, and path decompositions of each of them can be found far more simply than
trying to decompose the whole graph at once. By  nding decompositions of these subgraphs,
and by carefully using the partition of the element set to ensure that every edge of the graph
appears in exactly one of these subgraphs, all of the edges in the overall graph can be placed
into paths.
The construction technique in Chapter 4, where embeddings of partial 3-path systems
are considered, uses a similar approach. The key observation here is that maximal partial 3-
path systems have easily catalogued leaves. For embedding partial 3-path systems of order n
into complete 3-path systems of orders at least n+2, by carefully partitioning the components
of the leave the embedding problem can be reduced to  nding 3-path decompositions of a
reasonably small number of fairly basic graphs. In the case of embedding partial 3-path
5
systems or order n into complete 3-path systems of order n + 1, a di erent approach was
needed. Here, the problem is solved for maximal partial 3-path systems by analyzing what
the new 3-paths would look like in terms of how many edges in the leave they would use.
From here, the leave is partitioned into the proper number of paths of length two and paths
of length one, and the 3-paths required are built up from these smaller paths by taking
advantage of the predictable form of the leave.
6
Chapter 2
P3-decompositions of KGn;2 and GKGn;3;1
2.1 Introduction
In this chapter, the problem of  nding necessary and su cient conditions for obtaining
3-path decompositions of KGn;2 and GKGn;3;1 is completely solved. Recall that Tk(V) is
the set of k-element subsets of the set V, and let (a;b;c;d) denote the path, P3, of length
three with edge set ffa;bg;fb;cg;fc;dgg.
2.2 Building Blocks
The following lemmas will be useful in the constructions to come.
Lemma 2.1. There exists a P3-decomposition of each of the following graphs:
(i) K2;3
(ii) K3;3
(iii) Kn;3k for any n 2 and k 1
(iv) H4 = K3;3 F with bipartition fZ3;Z6nZ3g of V(K3;3), and where E(F) =ffi;i+ 3gj
i2Z3g
(v) H5 = H4[G0, where G0 = (Z9nZ3;ff3;6g;f4;7g;f5;8gg)
(vi) H6, the bipartite graph with bipartition fT2(Z4);Z4g of V(H6) and E(H6) = ffa;bgj
b =2a;a2T(Z4);b2Z4g
(vii) KG5;2 (the Petersen Graph)
7
(viii) H8, the bipartite graph with bipartition fT2(Z5);Z5g of V(H8) and E(H8) = ffa;bgj
b =2a;a2T(Z5);b2Z5g
Proof. Ho man and Billington solved cases (i)-(iii) (and much more besides) in [5]. However,
in the interest of keeping this discussion self-contained, explicit constructions are given for
these cases.
(i) De ne K2;3 with bipartition fZ2;Z5nZ2g of the vertex set Z5. Then
(Z5;f(0;2;1;3);(3;0;4;1)g) is the required decomposition.
(ii) De ne K3;3 with bipartition fZ3;Z6nZ3g of the vertex set Z6. Then
(Z6;f(3;0;5;2);(1;3;2;4);(0;4;1;5)g) is the required decomposition.
(iii) Since n  2, form a partition, P, of Zn into sets of size 2 and 3, and a parti-
tion Q of Zn+3knZn into sets of size 3. For each p 2 P and q 2 Q, let (p[
q;Bp;q) be a P3-decomposition of Kjpj;3 with bipartition fp;qg of the vertex set. Then
(Zn+3k;Sp2P;q2QBp;q) is the required P3-decomposition of Kn;3k.
(iv) With bipartition fZ3;Z6nZ3g, (Z6;f(0;4;2;3);(0;5;1;3)g) is the required decomposi-
tion with F =ff0;3g;f1;4g;f2;5gg.
(v) (Z9;f(6;3;1;5);(7;4;2;3);(8;5;0;4)g) is the required decomposition.
(vi) (V(H6);f(0;f2;3g;1;f0;2g);(1;f0;3g;2;f1;3g);(2;f0;1g;3;f0;2g);
(3;f1;2g;0;f1;3g)) is the required decomposition.
(vii) Let V(KG5;2) = T2(Z5). Then (T2(Z5);f(fi;i+1g;fi+2;i+3g;fi+1;i+4g;fi;i+3g)j
i2Z5g reducing the sums modulo 5 is the required decomposition.
(viii) (V(H8);f(1;f0;2g;3;f0;1g);(2;f0;3g;4;f0;2g);(2;f0;4g;1;f0;3g);
(0;f1;2g;3;f0;4g);(0;f1;3g;4;f1;2g);(3;f1;4g;2;f1;3g);
(4;f2;3g;0;f1;4g);(3;f2;4g;1;f2;3g);(1;f3;4g;0;f2;4g);(4;f0;1g;2;f3;4g)) is the re-
quired decomposition.
8
A graph, G, is said to have an Euler tour if there exists a closed walk in G that contains
each edge of G exactly once.
The following is well known.
Lemma 2.2. A connected simple graph, G, has an Euler tour if and only if the degree of
every vertex in G is even.
From this, we can easily obtain the following result.
Lemma 2.3. If G is a connected bipartite simple graph in which the number of edges is
divisible by three and all vertices have even degree, then G has a P3-decomposition.
Proof. By Lemma 2.2, let P = (v0;v1;:::;ve) be an Euler tour of G. Since G is bipartite,
each set of three consecutive edges of P induce a P3. Therefore, since e =jE(G)jis divisible
by three, (V(G);f(v3i;v3i+1;v3i+2;v3i+3)ji2Ze=3g) is a P3-decomposition of G.
Lemma 2.4. There exists a P3-decomposition of each of the following graphs:
(i) GKG5;3;1 (The Petersen Graph)
(ii) GKG6;3;1
Proof.
(i) GKG5;3;1 = KG5;2 as can be seen by taking the complement of each vertex. The result
follows from Lemma 2.1(vii).
(ii) Partition the vertices of GKG6;3;1 into the following two types:
Type 1: T3(Z5), and
Type 2: T3(Z6)nT3(Z5)
Let G1 be the subgraph induced by the Type 1 vertices, G2 be the subgraph induced
by the Type 2 vertices, and G3 be the bipartite subgraph induced by the edges of
the form fx;yg where x is a Type 1 vertex and y is a Type 2 vertex. G1 is clearly a
9
GKG5;3;1 and has a P3-decomposition by (i). G2 is isomorphic to KG5;2 (all vertices
share the element 5, so two are adjacent only if their other two elements are disjoint)
and has a P3-decomposition by Lemma 2.1(vii). G3 is a bipartite graph that is 6-
regular, so jE(G3)j is a multiple of three. To see that G3 is connected, for each Type
1 vertex, fa;b;cg in G3 we display a path to each vertex of Type 2 as follows (where
a;b;c;d and e are the distinct elements of Z5): (fa;b;cg;fa;d;5g;fb;c;dg;fa;b;5g),
(fa;b;cg;fa;d;5g;fa;b;eg;fd;e;5g), and (fa;b;cg;fa;d;5g). These account for all
pairs of nonadjacent vertices in G3, so G3 is connected. Therefore, G3 is a connected
even regular bipartite graph with a multiple of three edges, so by Lemma 2.3, it also has
aP3-decomposition. The union of these three decompositions forms aP3-decomposition
of GKG6;3;1.
2.3 A P3-Decomposition of KGn;2
Theorem 2.1. KGn;2 is P3-decomposable if and only if n6= 4.
Proof. If n2f1;2;3g, then KGn;2 has no edges, so the result is vacuously true. Since
KG4;2 is a 1-factor on six vertices, it is clearly not P3-decomposable. KG5;2 is decomposable
by Lemma 2.1(vii).
The remaining cases are proved by induction on n. So now assume that KGw;2 is
P3-decomposable for all w  n for some n  5. It is shown that G = KGn+1;2 is
P3-decomposable. Let  2f0;1;2g such that   n (mod 3). Let (T2(Zn);B) be a P3-
decomposition of KGn;2.
The subgraph of KGn+1;2 induced by vertices in T2(Zn+1)nT2(Zn) clearly has no edges,
since they all share the element n. What remains to be shown is that the subgraph in-
duced by the edges connecting vertices in T2(Zn) to vertices in T2(Zn+1)nT2(Zn) has a P3-
decomposition.
Partition Zn into t = (n  )=3 sets: Si = f3i;3i + 1;3i + 2g for i 2 Zt 1 and
St 1 =fijn 3   i n 1g. It is convenient to partition the old vertices, T(Zn), into
10
V
i
V
i,j
S
i
OldVertices NewVertices
Figure 2.1: Partitioning the Vertices
the following two types (visualized in Figure 2.1):
Vi =ffx;ygjx;y2Si;x6= yg for i2Zt, and
Vi;j =ffx;ygjx2Si;y2Sjg for 0 i<j <t.
Further, partition the new vertices into t sets:
S0i =ffx;ngjx2Sig for i2Zt.
All of the edges not involving vertices with elements in St 1 are handled  rst. Of these
edges, the edges that require special attention are those joining two vertices in ffv;sgjv2
Vi;s 2 S0ig for some i 2 Zt 1 . For each i 2 Zt 1, these edges induce a matching on six
vertices, so they can?t be decomposed into three paths in isolation. To decompose these
edges, they are combined with edges joining two vertices in ffv;sgjv 2V0;i;s2S0ig for
some i2Zt 1nf0gto form 3-paths as described in the next two paragraphs, with i = 1 being
an even more special case.
11
{5,n}
{4,n}
{3,n}
Sprime1V0,1
{0,3} {1,3} {2,3}
{0,4} {1,4} {2,4}
{0,5} {1,5} {2,5} {3,4}
{3,5}
{4,5}
V1
{2,n}{1,n}{0,n} Sprime0
{0,1}{0,2}{1,2} V0
Figure 2.2: The Two H5?s
{5,n}
{4,n}
{3,n}
Sprime1V0,1
{0,3} {1,3} {2,3}
{0,4} {1,4} {2,4}
{0,5} {1,5} {2,5} {3,4}
{3,5}
{4,5}
V1
{2,n}{1,n}{0,n} Sprime0
{0,1}{0,2}{1,2} V0
Figure 2.3: Example of the H4
First, consider the bipartite subgraph G0 of KGn+1;2 induced by the edges joining the
vertices in V0[V1[V0;1 to the vertices in S00[S01. Partition these edges as follows. The
edges joining the vertices of V1 [ff0;xgj x 2 S1g to S01 induce a subgraph isomorphic
to H5, so by Lemma 2.1(v), there exists a P3-decomposition of this subgraph. The edges
joining the vertices of V0[ffx;3gjx2S0g to S00 also form a subgraph isomorphic to H5,
so by Lemma 2.1(v), there exists a P3-decomposition of this subgraph as well (See Figure
2.2). Now, for each k2f1;2g consider the edges joining the vertices ffk;xgjx2S1g to
the vertices in S01. These edges induce a subgraph isomorphic to H4, so by Lemma 2.1(iv),
there exists a P3-decomposition of this subgraph. Also, for each k2f4;5gthe edges joining
the vertices ffx;kgjx2S0g to the vertices in S00 induce a subgraph isomorphic to H4, so
by Lemma 2.1(iv), there exists a P3-decomposition of this subgraph (See Figure 2.3 for an
example). Figure The union of these sets of 3-paths produce a P3-decomposition (V(G0);B00)
of most of G0. The edges connecting V1 to S00 and connecting V0 to S01 occur in paths in B01;0
and B00;1, respectively as de ned below.
Now, for each i2fZt 1nZ2g, consider the bipartite subgraph Gi of KGn+1;2 induced
by the edges joining the vertices in Vi[V0;i to the vertices in S00 [S0i. The edges in Gi
connecting the vertices of Vi[ff0;xgjx2Sig to S0i induce a subgraph isomorphic to H5,
thus it has a P3-decomposition by Lemma 2.1(v). Now, for each k2f1;2g, the edges joining
12
the vertices in ffk;xgjx2Sig to the vertices in S0i induce a subgraph isomorphic to H4,
so there exists a P3-decomposition of the subgraph by Lemma 2.1(iv). Further, for each
k2Si, the edges connecting the vertices of ffx;kgjx2S0g to the vertices of S00 induce
a subgraph isomorphic to H4 which therefore has a decomposition by Lemma 2.1(iv). The
union of these decompositions produce a P3-decomposition, (V(Gi);B0i), of most of Gi for
each i2fZtnZ2g. The remaining edges in Gi, namely those connecting Vi to S00, are in paths
in B0i;0 as de ned below.
For each i2Zt 1 and for each j 2Zt 1nfig, the bipartite subgraph of G induced by
the edges joining vertices in Vi to vertices in S0j is isomorphic to K3;3, so by Lemma 2.1(ii)
there exists a P3-decomposition (Vi[S0j;B0i;j) of this subgraph.
For 1 <j <t 1, the edges connecting vertices of V0;1 to vertices of S0j induce a K9;3 ,
and thus this graph has a P3-decomposition (V0;1[S0j;B0;1;j) by Lemma 2.1(iii).
For each i 2 Zt 1nZ2 and for each j 2 Zt 1nf0;ig, the edges connecting vertices of
V0;i with the vertices of S0j induce a copy of K9;3 so this graph has a P3-decomposition,
(V0;i[S0j;B0;i;j), by Lemma 2.1(iii).
For 0 <i<j <t 1 and 0 k <t 1, consider the bipartite subgraph of G induced
by edges joining vertices in Vi;j to vertices in S0k. This subgraph of G has a P3-decomposition
as follows:
(a) if k =2fi;jg, then the subgraph is isomorphic to K9;3, so it has a P3-decomposition
(Vi;j[S0k;Bi;j;k) by Lemma 2.1(iii);
(b) if k = i, then for each y2Sj the edges connecting the vertices ffx;ygjx2Sig and
S0k=i induce a subgraph isomorphic toH4, which has aP3-decomposition (Vi;j[S0k;Bi;j;k)
by Lemma 2.1(iv);
(c) if k = j, then for each x2Si the edges connecting the vertices ffx;ygjy2Sjg and
S0k=j form a subgraph isomorphic to H4, which has a P3-decomposition (Vi;j[S0k;Bi;j;k)
by Lemma 2.1(iv).
13
The only edges left to consider are all the edges which are incident with a vertex in
S0t 1[Vt 1[Vi;t 1, i2Zt 1. The handling of these edges depends on the value of  .
First, consider the bipartite subgraph Gt 1 of KGn+1;2 induced by the edges joining the
vertices in Vt 1[V0;t 1 to the vertices in S00[S0t 1. We consider each value of  in turn.
For  = 0, the edges in Gt 1 connecting the vertices of Vt 1[ff0;xgjx2St 1gto S0t 1
induce a subgraph isomorphic to H5, thus it has a P3-decomposition by Lemma 2.1(v). Now,
for each k2f1;2g, the edges joining the vertices inffk;xgjx2St 1gto the vertices in S0t 1
induce a subgraph isomorphic to H4, so there exists a P3-decomposition by Lemma 2.1(iv).
Further, for each k 2 St 1, the edges connecting the vertices of ffx;kgj x 2 S0g to the
vertices of S00 induce a subgraph isomorphic to H4 which therefore has a decomposition by
Lemma 2.1(iv). Lastly, the edges joining the vertices in vt 1 to the vertices in S00 induce a
subgraph isomorphic to K3;3, and so has a P3-decomposition be Lemma 2.1(ii). The union
of these decompositions produce a P3-decomposition, (V(Gt 1);B0t 1), of Gt 1.
For  = 1 or 2, the edges connecting vertices in Vt 1 to S0t 1 induce a graph isomorphic to
H6 or H8 respectively, which has a P3-decomposition by Lemma 2.1(vi)((viii) respectively).
Regarding the edges connecting vertices in V0;t 1 to S0t 1, for each y2St 1 the edges con-
necting the verticesffx;ygjx2S0gand S0t 1 induce a subgraph isomorphic to K3;3 if  = 1
and K3;4 if  = 2, which has a P3-decomposition by Lemma 2.1(iii) in both cases. For each
k2St 1 the edges connecting the vertices in ffx;kgjx2S0g to the vertices in S00 induce
a subgraph isomorphic to H4, so there exists a P3-decomposition by Lemma 2.1(iv). Lastly,
the edges joining the vertices in vt 1 to the vertices in S00 induce a subgraph isomorphic to
K3+ ;3, and so has a P3-decomposition be Lemma 2.1(iii). The union of these decompositions
produce a P3-decomposition, (V(Gt 1);B0t 1), of Gt 1.
The rest of the edges are easier to decompose.
For each i2Zt 1, the bipartite subgraph induced by the edges joining the vertices of
Vi to the vertices of S0t 1 induce a graph isomorphic K3;3+ , so it has a P3-decomposition
(Vi[S0t 1;Bi;t 1) by Lemma 2.1(iii).
14
For 0 i<j <t 1, the bipartite subgraph induced by the edges joining the vertices of
Vi;j to the vertices of S0t 1 induce a graph isomorphic to K9;3+ , so it has a P3-decomposition
(Vi;j[S0t 1;Bi;j;t 1) by Lemma 2.1(iii).
Finally, For 0 <i<t 1 and 0 k<t, consider the bipartite subgraph of G induced by
edges joining vertices in Vi;t 1 to vertices in S0k. This subgraph of G has a P3-decomposition
as follows:
(a) ifk =2fi;t 1g, then the subgraph is isomorphic toK3(3+ );3, so it has aP3-decomposition
(Vi;t 1[S0k;Bi;t 1;k) by Lemma 2.1(iii);
(b) if k = i, then for each y 2 St 1 the edges connecting the vertices ffx;yg j x 2
Sig and S0k=i induce a subgraph isomorphic to H4, which has a P3-decomposition
(Vi;t 1[S0k;Bi;t 1;k) by Lemma 2.1(iv);
(c) if k = t 1, then
Case  = 0: For each x2Si the edges connecting the vertices ffx;ygjy2Sjg
and S0k=j induce a subgraph isomorphic to H4, which has a P3-decomposition
(Vi;j[S0k;Bi;j;k) by Lemma 2.1(iv).
Case  = 1: For each y2St 1 the edges connecting the vertices ffx;ygjx2Sig
and S0k=t 1 induce a subgraph isomorphic to K3;3, which has a P3-decomposition
(Vi;t 1[S0k;Bi;t 1;k) by Lemma 2.1(ii).
Case  = 2: For each y2St 1 the edges connecting the vertices ffx;ygjx2Sig
and S0k=t 1 induce a subgraph isomorphic to K4;3, which has a P3-decomposition
(Vi;t 1[S0k;Bi;t 1;k) by Lemma 2.1(iii).
This accounts for all new edges.
15
Let B1 = Si2ZtB0i, B2 = S0 i<j<tB0i;j, and B3 = S0 i<j<t;k2ZtB0i;j;k. The required
P3-decomposition of G is given by (V(G);B[B1[B2[B3).
2.4 A P3-Decomposition of GKGn;3;1
Before stating and proving the main result forGKGn;3;1, a few de nitions and a technical
lemma are presented.
A digraph is an ordered quadruple D = (V;E;t;h) where V is a set of vertices, E is a
set of ordered pairs of vertices (each element of which is called an arc or directed edge), and
t;h : E!V are functions de ned by t((u;v)) = u and h((u;v)) = v for each arc (u;v)2E
(t(e) and h(e) are called the tail and head of arc e, respectively). A complete digraph is a
digraph in which E = V  V.
A directed 2-factor of a digraph D is a spanning subdigraph F in which every vertex is
the head of exactly one arc and the tail of exactly one arc of F.
Let D = (V;E;t;h) be a digraph, let C be a set of colors, and for each e 2 E, let
Ce  C. A (C1;:::;Ce)-coloring of D is a function c : E ! C such that if e 2 E then
c(e)2Ce (this is known as a list arc-coloring). A list arc-coloring is said to be proper if no
two adjacent arcs receive the same color. In the following lemma, the vertex set is T3(Zn), so
we can refer to the intersection of two vertices (it is the intersection of two 3-element sets).
Lemma 2.5. Let D = (T3(Zn);E;t;h) be a complete digraph. Let C = Zn be a set of
colors. For each e2E, let Ce = t(e)\h(e) (so possibly Ce =;). There exists a proper list
arc-colored directed 2-factor of D.
Proof. Let D, C, and Ce be de ned as stated in the lemma. Form a directed 2-factor, F, of
D as follows.
First, form a partition, P, of the vertex set T3(Zn) so that two vertices fa;b;cg and
fx;y;zg are in the same element of P if and only if fx;y;zg=fa + i;b + i;c + ig for some
i2Zn with the sums reduced modulo n. If n is not a multiple of three, then P contains
16
l = (n 1)(n 2)6 sets, each containing n elements. If n is a multiple of three, say n = 3k,
then P contains l = (
3k
3 ) k
3k = 3
 k
2
 sets of size n and one set of size k. In either case, let
the elements of P of size n be fE0;E1;:::El 1g, and if n is a multiple of three then let
El =ffi;i+k;i+ 2kgji2Zkg be the single set of size k.
For 0  i < l, among the vertices in Ei, let ei = f0;ai;big with ai < bi be one that
contains both zero and as small a nonzero element of Zn as possible (two such vertices might
exist, in which case either can be ei). Let di = gcd(ai;n). For 0 j <di, and for 0 r< ndi,
de ne the arc ei;r;j = (frai+j;(r+1)ai+j;rai+bi+jg;f(r+1)ai+j;(r+2)ai+j;(r+1)ai+
bi+jg) in D. Then for each j2Zdi, the subgraph Si;j of D induced byfei;r;jj0 r< ndigis
a directed cycle. Note that the both the tail and head of each arc ei;r;j contains the element
(r + 1)ai +j; so let c(ei;r;j) = (r + 1)ai +j. Clearly this coloring is proper since consecutive
arc colors di er by ai (mod n), where clearly ai < n. If n is not a multiple of three, then
F = Si2Zl;j2Zd
i
Si;j is a directed 2-factor that is properly list arc-colored as required.
If n is a multiple of three, then F is a properly list arc-colored directed 2-factor that
includes all of the vertices in D except for those in El. We now insert the k vertices in El
into an already created directed cycle in F and then give a proper list arc-coloring to the
modi ed cycle. Recall that El =fi;k+i;2k+igj0 i<kg. Consider the colored directed
cycle, C0, in F containing the vertex f0;1;1 + kg. Then C0 = (v00;v01;:::;v0n 1) where for
each j2Zn, v0j =f0 + j;1 + j;1 + k + jg and where the arc (v0j;v0j+1) is colored j + 1. For
0 j k, replace the arc (f0 +j;1 +j;1 +k +jg;f1 +j;2 +j;2 +k +jg) colored i+j in
F with the arcs (f0 +j;1 +j;1 +k+jg;f1 +j;1 +k+j;1 + 2k+jg) colored 1 +k+j and
(f1 +j;1 +k+j;1 + 2k+jg;f1 +j;2 +j;2 +k+jg) colored 1 +j. The resulting cycle is still
properly list edge-colored since the only potential con ict is at the vertexf0;1;1 +kgwhich
previously was incident with arcs colored 0 and 1 and now is incident with arcs colored 0
and 1 +k.
We are now ready to prove our second main result.
Theorem 2.2. G = GKGn;3;1 has a P3-decomposition for all n> 0.
17
Proof. For n2f1;2;3;4g, G has no edges, so the result is vacuously true. For n = 5, G has a
P3-decomposition by Lemma 2.4(i). For n = 6, G has a P3-decomposition by Lemma 2.4(ii).
The remaining cases are proved by induction on n. So now assume that GKGw;3;1
is P3-decomposable for all w  n for some n  6. It is shown that H = GKGn+2;3;1 is
P3-decomposable. Let (T3(Zn);B0) be a P3-decomposition of G = GKGn;3;1. Partition the
vertices of H as follows:
(i) V0 = T3(Zn) (the vertices of G),
(ii) V1 =ffa;b;ngja;b2Zng,
(iii) V2 =ffa;b;n+ 1gja;b2Zng, and
(iv) V3 =ffa;n;n+ 1gja2Zng.
Consider the following subgraphs of H:
(i) H0 is the subgraph induced by the vertices of V0,
(ii) H1 is the subgraph induced by the vertices of V1[V3,
(iii) H2 is the subgraph induced by the vertices of V2[V3,
(iv) H3 is the bipartite subgraph induced by the edges ffx;ygjx2V0;y2V1[V2g,
(v) H4 is the bipartite subgraph induced by the edges ffx;ygjx2V1;y2V2g, and
(vi) H5 is the bipartite subgraph induced by the edges ffx;ygjx2V0;y2V3g.
These six subgraphs clearly partition the edges of H, so combining P3-decompositions of
each will create a P3-decomposition of H itself.
Since H0 = G, it has a decomposition (T3(Zn);B0) by assumption.
Next, notice that in H1 and H2, all vertices share the element x = n or n+1 respectively;
so any two vertices, say fa;b;xgand fc;d;xg, are adjacent if and only if fa;bg\fc;dg=;.
So H1 is clearly isomorphic to KGn+1;2 with vertex set fvnfngj v 2 V(H1)g and H2 is
18
isomorphic to KGn+1;2 with vertex setfvnfn+ 1gjv2V(H2)g. Therefore, H1 and H2 have
P3-decompositions (V(H1);B1) and (V(H2);B2) respectively by Theorem 2.1.
Next, consider the bipartite subgraph H3. If v 2 V0, then dH3(v) = 6 n 32  , and if
v2V1[V2, then dH3(v) = 2 n 22  , both of which are even. Also,jE(H3)j= 6 n2  n 32  which
is clearly a multiple of three. Finally, to show H3 is connected, for each fs;t;ug2V0 we
display a path to each vertex in V1[V2 as follows (where a;b;s;t, and u are distinct elements
of Zn and x2fn;n+ 1g): (fs;t;ug;fa;s;xg;
fb;s;ug;fa;b;xg), (fs;t;ug;fa;s;xg;fa;b;tg;fs;t;xg), and (fs;t;ug;fa;s;xg).
These account for all pairs of nonadjacent vertices in H3, so H3 is easily seen to be connected.
Therefore, H3 has a P3-decomposition (V(H3);B3) by Lemma 2.3.
We also use Lemma 2.3 to  nd a P3-decomposition of H4 as the following shows. H4 is
a 2 n 22  -regular bipartite graph, so all vertices have even degree. Also,jE(H4)j= 2 n2  n 22  
which is a multiple of three. To see this, note jE(H4)j is the product of four consecutive
integers (one of which must be a multiple of three) divided by two. Finally, to show that H4
is connected, for each vertex fa;b;ng2V1 we display a path to each vertex in V2 as follows
(where a;b;s, and t are distinct elements of Zn): (fa;b;ng;fa;t;n+1g;fa;s;ng;fa;b;n+1g),
(fa;b;ng;fb;s;n+ 1g;fa;s;ng;fs;t;n+ 1g), and (fa;b;ng;fa;c;n+ 1g). These account for
all pairs of nonadjacent vertices in H4, so H4 is easily seen to be connected. Therefore, H4
has a P3-decomposition (V(H4);B4) by Lemma 2.3.
Finally, consider H5. Using Lemma 2.5, let F be a properly list arc-colored 2-factor of
the complete digraph with vertex set V0, with the set of colors C = Zn, and with lists of colors
(C0;C1;:::;CjEj 1) de ned by Ce = t(e)\h(e) for each e2E. Assume F has components
ff0;f1;:::;fm 1g. For each i2Zm, consider the directed cycle fi of length l with E(fi) =
fe0;e1;:::;el 1g where h(ek) = t(ek+1) for k2Zl with additions done modulo l. Form the
following 3-paths in H5: Ti = f(t(ej);fc(ej);n;n + 1g;h(ej);fh(ej)nfc(ej);c(ej+1)g;n;n +
1g)jj2Zlgwith subscript additions done modulo l. The edges in Ti exist in H5 since Ce is
a list of the shared elements of t(e) and h(e). H5 has a P3-decomposition (V(H5);B5) where
19
B5 = Si2ZmTi. To see that each edge in H5 is in exactly one path in B5, consider the edge
e = (fa;b;cg;fa;n;n+ 1g) in H5. The vertexfa;b;cgis in exactly one component, fi, of F.
Consider the two arcs, e1 and e2 in fi such that h(e1) =fa;b;cgand t(e2) =fa;b;cg. There
are three possibilities.
1. If c(e1) = a, then e is in (t(e1);fa;n;n+ 1g;fa;b;cg;ffb;cgnc(e2);n;n+ 1).
2. Ifc(e2) = a, then lete3 be the arc infi witht(e3) = h(e2). Theneis in (fa;b;cg;fa;n;n+
1g;h(e2);fh(e2)nfa;c(e3)g;n;n+ 1g).
3. If a =2fc(e1);c(e2)g, the e is in (t(e1);fc(e1);n;n+ 1g;fa;b;cg;fa;n;n+ 1g).
Since F is a properly list arc-colored 2-factor, exactly one of the previous three cases holds.
Thus every edge of H5 is in exactly one path in B5.
Let B = Si2Z6 Bi. Then (V(H);B) is the desired P3-decomposition.
20
Chapter 3
P4-decompositions of KGn;2
3.1 Introduction
In this chapter, the problem of  nding necessary and su cient conditions for obtaining
4-path decompositions of KGn;2 is completely solved. Again, recall that Tk(V) is the set of
k-element subsets of the set V, and let (a;b;c;d;e) denote the path, P4, of length four with
edge set ffa;bg;fb;cg;fc;dg;fd;egg.
3.2 Useful Building Blocks
Billington and Ho man solved a more general problem concerning P4-decompositions
of multipartite graphs [5], but the following will su ce for our purposes.
Lemma 3.1. The complete bipartite graph Ka1;a2 with a1  a2 has a P4-decomposition if
and only if a1  2, a2  3 and a1a2  0 (mod 4).
The next result provides speci c ingredients used in the general constructions.
Lemma 3.2. There exists a P4-decomposition of:
(i) the bipartite graph H1 with partition fA = T2(Z4);B = Z4g of V(H1) and E(H1) =
ffa;bgja2A;b2B;b =2ag,
(ii) the bipartite graph H2 with partition fA = T2(Z6);B = Z6g of V(H2) and E(H2) =
ffa;bgja2A;b2B;b =2ag,
(iii) H3(W;X;Y) = (W[X[Y;E), where W, X, and Y are disjoint sets of size 4, and
E =ff(i1;l1);(i2;l2)gjl1 6= l2;i1 2X[Y;i2 2Wg,
21
(iv) H4 = (Z4 Z4;f(i;j);(k;l)ji6= k;j6= lg),
(v) H5(W;X;Y;Z) = (W[X[Y[Z;E), where W, X, Y, and Z are disjoint sets of size
4, and E =ff(i1;l1);(i2;l2)gjl1 6= l2;i1 2X[Y [Z;i2 2Wg,
(vi) the bipartite graph H6 with partition fA = T2(Z5)[T(Z9nZ5);B = Z5g of V(H6) and
E(H6) =ffa;bgja2A;b2B;b =2ag, and
(vii) K8.
Proof.
(i) (V(H1);f(0;f1;2g;3;f0;1g;2);(3;f0;2g;1;f2;3g;0);(0;f1;3g;2;f0;3g;1)g) is the re-
quired decomposition.
(ii) Let B1 =f(1 + 3i;f3i;2 + 3ig;5 + 3i;f1 + 3i;2 + 3ig;4 + 3i);(3 + 3i;f3i;2 + 3ig;4 +
3i;f3i;1 + 3ig;5 + 3i);(2 + 3i;f3i;1 + 3ig;3 + 3i;f1 + 3i;2 + 3ig;3i) j i 2f0;1gg
with addition done modulo 6 and B2 = f(j + 1;fj;3g;4;fj;5g;j + 2);(fj;3g;j +
2;fj;4g;3;fj;5g);(fj;3g;5;fj;4g;j+1;fj;5g)jj2f0;1;2ggwith addition done mod-
ulo 3. Then (V(H2);B1[B2) is the required decomposition.
(iii) Let W = fw1;w2;w3;w4g, X = fx1;x2;x3;x4g, and Y = fy1;y2;y3;y4g. Then
(W[X[Y;f(x1;w3;x4;w1;x3);(x2;w4;x3;w2;x4);(y1;w3;y2;w1;y4);
(y2;w4;y1;w2;y3);(w1;x2;w3;y4;w2);(w1;y3;w4;x1;w2)g) is the required decomposi-
tion.
(iv) The result follows from (iii), since H4 is the union of the three graphs H3(Z4 fig;Z4 
fjg;Z4 fkg), where (i;j;k)2f(1;0;2);(3;2;1);(0;3;2)g
(v) LetW =fw1;w2;w3;w4g, X =fx1;x2;x3;x4g, Y =fy1;y2;y3;y4g, andZ =fz1;z2;z3;z4g.
Then (W[X[Y [Z;f(x0;w2;x1;w0;x2);
(x1;w3;x2;w1;x3);(y0;w1;y2;w0;y1);(y3;w2;y1;w3;y2);(z1;w0;z2;w1;z3);
22
(z2;w3;z1;w2;z3);(z3;w0;y3;w1;z0);(w2;z0;w3;x0;w1);(w0;x3;w2;y0;w3)g) is the re-
quired decomposition.
(vi) (V(H6);f(f0;1g;3;f0;2g;4;f5;6g);(f0;2g;1;f0;3g;4;f5;7g);
(f0;3g;2;f0;4g;1;f6;8g);(f0;4g;3;f1;2g;4;f5;8g);
(f1;2g;0;f1;3g;4;f6;7g);(f1;3g;2;f1;4g;3;f6;8g);
(f1;4g;0;f2;3g;4;f6;8g);(f2;3g;1;f2;4g;3;f7;8g);
(f2;4g;0;f3;4g;1;f7;8g);(f3;4g;2;f0;1g;4;f7;8g);
(f5;6g;1;f5;7g;3;f5;8g);(f5;6g;3;f6;7g;1;f5;8g);
(f5;6g;0;f5;7g;2;f5;8g);(f5;6g;2;f6;7g;0;f6;8g);
(f6;8g;2;f7;8g;0;f5;8g)g) is the required decomposition.
(vii) De ne K8 on the vertices Z7[f1g. Then (Z7[f1g;f(1;i;i+1;i 1;i+2)ji2Z7g)
with addition done modulo 7 is the required decomposition.
Since the proof of Theorem 3.1 is based on a recursive construction, the next result gives
an important starting point.
Lemma 3.3. KG16;2 is P4-decomposable.
Proof. Consider G = KG16;2 on vertex set T(Z16). Partition Z16 into four sets
Si = f4i;4i + 1;4i + 2;4i + 3g for i 2 Z4. Partition the set of vertices T(Z16) of G into
the following two types:
Type 1: Vi =ffx;ygjx;y2Si;x6= yg for each i2Z4, and
Type 2: Vi;j =ffx;ygjx2Si;y2Sjg for 0 i<j < 4.
First, the subgraph G0 of G induced by the Type 1 vertices is considered. Decompose
G0 into paths of length four in two steps. First de ne three pairs of vertices M0;i =ff4i;4i+
23
K8
K8
K8
V0 V1 V2 V3
{0,1}
{2,3}
{1,3}
{0,2}
{0,3}
{1,2}
{4,5}
{6,7}
{4,6}
{5,7}
{4,7}
{5,6}
{8,9}
{10,1}
{8,10}
{9,1}
{8,1}
{9,10}
{12,13}
{14,15}
{12,14}
{13,15}
{12,15}
{13,14}
Figure 3.1: The K8?s
V
0
V
1
{0,1}
{2,3}
{1,3}
{0,2}
{0,3}
{1,2}
{4,5}
{6,7}
{4,6}
{5,7}
{4,7}
{5,6}
Figure 3.2: B0;1;j
1g;f4i+ 2;4i+ 3gg, M1;i =ff4i;4i+ 2g;ff4i+ 1;4i+ 3gg, and M2;i =ff4i;4i+ 3g;ff4i+
1;4i + 2gg. For each j2Z3, the subgraph G0j of G0 induced by Si2Z4 Mj;i is isomorphic to
K8 (Figure 3.1) which therefore has a P4-decomposition (Si2Z4 Mj;i;B0j) by Lemma 3.2(vii).
Let B1 = Sj2Z3 B0j. Second, for 0  i1 < i2  3 and for j 2 Z3, the induced bipartite
subgraph G0i1;i2;j of G0 with bipartitionfMj;i1;Sk2Z3nfjgMk;i2gis isomorphic to K2;4 so has a
P4-decomposition (V(G0i1;i2;j);B0i1;i2;j) by Lemma 3.1. Let B2 = S0 i1<i2 3;j2Z3 B0i1;i2;j. (See
Figure 3.2 for an example of the decomposition of the other edges beteween V0 and V1).
All edges connecting Type 1 vertices have now been placed into 4-paths in B1[B2. The
remaining edges are those connecting Type 2 vertices and those connecting a Type 1 vertex
to a Type 2.
The subgraph Gi;j of G induced by the vertices in Vi;j for 0 i<j < 4 is isomorphic
to H4, so has a P4-decomposition (V(Gi;j);Bi;j) by Lemma 3.2(iv). Let B3 = S0 i<j<4Bi;j.
Next, consider the subgraph Gi;j;k of G induced by the edges joining the vertices in Vi;j
to the vertices in Vk where 0 i<j < 4 and k2Z4. If k =2fi;jg, then Gi;j;k is isomorphic
to K16;6 and has a P4-decomposition (V(Gi;j;k);Bi;j;k) by Lemma 3.1. If k 2fi;jg then
without loss of generality assume that k = i. Then Gi;j;k consists of four edge disjoint copies
of K3;4 (induced by the edges connecting vertices in ffx;ygj y 2 Sjg to vertices in Vk
for each x2Si=k). So Gi;j;k has a P4-decomposition (V(Gi;j;k);Bi;j;k) by Lemma 3.1. Let
B4 = S0 i<j<4;k2Z4 Bi;j;k.
24
Finally, consider the subgraph Gi;j;k;l of G induced by the edges joining the vertices in
Vi;j to the vertices in Vk;l where 0  i < j < 4 , 0  k < l < 4, and jfi;jg\fk;lgj< 2.
If fi;jg\fk;lg = ;, then Gi;j;k;l is isomorphic to KG16;16 and so has a P4-decomposition
(V(Gi;j;k;l);Bi;j;k;l) by Lemma 3.1. If jfi;jg\fk;lgj = 1 then without loss of general-
ity assume that i = k. Then Gi;j;k;l consists of four edge disjoint copies of K4;12 (in-
duced by the edges connecting vertices in ffx;yg j y 2 Sjg to vertices in Vk;l for each
x 2 Si=k). So Gi;j;k;l has a P4-decomposition (V(Gi;j;k;l);Bi;j;k;l) by Lemma 3.1. Let
B5 = S0 i<j<4;0 k<l<4;jfi;jg\fk;lgj<2Bi;j;k;l
All of the edges have now been placed into 4-paths, thus (V(G);S1 i 5Bi) is a P4-
decomposition of G.
3.3 A P4-Decomposition of KGn;2
We are now ready to prove the main theorem.
Theorem 3.1. KGn;2 is P4-decomposable if and only if n 0;1;2 or 3 (mod 16).
Proof. The necessity follows from the observation that
jE(KGn;2)j= n(n 1)(n 2)(n 3)=8 is a multiple of 4 if and only if n 0;1;2 or 3 (mod
16).
If n 2f0;1;2;3g, then KGn;2 has no edges, so the result is vacuously true. KG16;2
has a P4-decomposition by Lemma 3.3. The remaining cases are proved by induction on n.
Suppose for some w 1 that for all t 16w with t 0;1;2 or 3 (mod 16) there exists a
P4-decomposition (V(KGt;2);B) of KGt;2. It remains to  nd a P4-decomposition of KGn;2
for each n =f16w + 1;16w + 2;16w + 3;16w + 16g.
First suppose n = 16w+16. By the inductive hypothesis there exists a P4-decomposition
(V(KG16w;2);B) of KG16w;2. Let X = fxi j i 2 Z16g and S = Z16w [X. Consider
G = KG16w+16;2 on the vertex set T(S). Partition S into 4w + 4 sets as follows: Si =
f4i;4i + 1;4i + 2;4i + 3g for i2Z4w and Xj = fx4j;x4j+1;x4j+2;x4j+3g for j2Z4. Using
this partition of S, partition the vertices of G into the following types:
25
(a) Vi =ffx;ygjx;y2Si;x6= yg for each i2Z4w,
(b) V0i =ffx;ygjx;y2Xi;x6= yg for each i2Z4,
(c) Vi;j =ffx;ygjx2Si;y2Sjg for 0 i<j < 4w,
(d) V0i;j =ffx;ygjx2Xi;y2Xjg for 0 i<j < 4, and
(e) Si;j =ffx;ygjx2Si;y2Xjg for each i2Z4w and each j2Z4.
It is convenient to refer to the vertices in (Si2Z4w Vi)[(S0 i<j<4wVi;j) as ?old? vertices
and the vertices in (Si2Z4 V0i )[(S0 i<j<4V0i;j) as ?new? vertices. Consider the subgraph
G1 of G induced by the old vertices. G1 is isomorphic to KG16w;2 and therefore has a P4-
decomposition (V(G1);B1) by the inductive hypothesis. The subgraph G2 of G induced
by the new vertices is isomorphic to KG16;2 and has a P4-decomposition (V(G2);B2) by
Lemma 3.3. The bipartite subgraph G3 of G formed by the edges ffx;ygj x is an old
vertex, y is a new vertexgis isomorphic to the complete bipartite graph K(16w
2 );(
16
2 )
and thus
has a P4-decomposition (V(G3);B3) by Lemma 3.1.
The only edges of G left to place into paths are those in the subgraph of G induced by
each Si;j, those connecting the vertices in each Si;j to the old and new vertices, and those
connecting vertices in each Si;j to vertices in each other Sk;l.
The subgraph Gi;j of G induced by the vertices in Si;j for i 2 Z4w and j 2 Z4 is
isomorphic to H4 and thus has a P4-decomposition (V(Gi;j);Bi;j) by Lemma 3.2(iv). Let
B4 = Si2Z4w;j2Z4 Bi;j.
For each i;k2Z4w and j2Z4, consider the bipartite subgraph Gi;j;k of G induced by
the edges joining the vertices in Si;j to the vertices in Vk. If i6= k then Gi;j;k is isomorphic
26
to K16;6 and has a P4-decomposition (V(Gi;j;k);Bi;j;k) by Lemma 3.1. If i = k then Gi;j;k
consists of four edge disjoint copies of K3;4 (induced by the edges connecting the vertices
in ffa;ygj y 2 Xjg to those in Vi=k for each a 2 Si). So in all cases Gi;j;k has a P4-
decomposition (V(Gi;j;k);Bi;j;k) by Lemma 3.1. Let B5 = Si;k2Z4w;j2Z4 Bi;j;k.
For each i2Z4w, j;k2Z4, consider the bipartite subgraph G0i;j;k of G induced by the
edges joining the vertices in Si;j to the vertices in V0k. If j 6= k, then G0i;j;k is isomorphic
to K16;6 and has a P4-decomposition (V(G0i;j;k);B0i;j;k) by Lemma 3.1. If j = k, then G0i;j;k
consists of four edge disjoint copies of K3;4 (induced by the edges connecting the vertices
in ffa;xgj a 2 Sig to those in V0k for each x 2 Xk). So G0i;j;k has a P4-decomposition
(V(G0i;j;k);B0i;j;k) by Lemma 3.1. Let B6 = Si2Z4w;j;k2Z4 B0i;j;k.
For each i;k;l 2 Z4w, k 6= l, and j 2 Z4, consider the bipartite subgraph Gi;j;k;l of
G induced by the edges joining the vertices in Si;j to the vertices in Vk;l. If i =2fk;lg,
then Gi;j;k;l is isomorphic to K16;16 and thus has a P4-decomposition (V(Gi;j;k;l);Bi;j;k;l) by
Lemma 3.1. If i2fk;lg then without loss of generality assume that i = k. Then Gi;j;k;l
consists of four edge disjoint copies of K12;4 (induced by the edges connecting the vertices
in ffa;ygjy2Xjg to those in Vi=k;l for each a2Si=k). So Gi;j;k;l has a P4-decomposition
(V(Gi;j;k;l);Bi;j;k;l) by Lemma 3.1. Let B7 = Si;k;l2Z4w;j2Z4;k6=lBi;j;k;l.
For each i 2 Z4w and j;k;l 2 Z4 with k 6= l, consider the bipartite subgraph G0i;j;k;l
of G induced by the edges joining the vertices in Si;j to the vertices in V0k;l. If j =2fk;lg,
then G0i;j;k;l is isomorphic to K16;16 and thus has a P4-decomposition (V(G0i;j;k;l);B0i;j;k;l) by
Lemma 3.1. If j 2fk;lg then without loss of generality assume that j = k. Then G0i;j;k;l
consists of four edge disjoint copies of K12;4 (induced by the edges connecting the vertices
in ffa;xgja2Sig to those in V0j=k;l for each x2Xj=k). So G0i;j;k;l has a P4-decomposition
(V(G0i;j;k;l);B0i;j;k;l) by Lemma 3.1. Let B8 = Si2Z4w;j;k;l2Z4;k6=lB0i;j;k;l.
Finally, for each i;k2Z4w and j;l2Z4 with i6= k and/or j6= l, consider the bipartite
subgraph S0i;j;k;l of G induced by the edges joining the vertices in Si;j to the vertices in
Sk;l. If fi;jg\fk;lg = ;, then S0i;j;k;l is isomorphic to K16;16 and has a P4-decomposition
27
(V(S0i;j;k;l);B0i;j;k;l) by Lemma 3.1. If i = k and j6= l, then S0i;j;k;l consists of four edge disjoint
copies of K12;4 (induced by the edges connecting the vertices in ffa;xgjx2Xjg to those
in S0i=k;l for each a2Si=k). If i6= k and j = l, then S0i;j;k;l consists of four edge disjoint
copies of K12;4 (induced by the edges connecting the vertices in ffa;xgja2Sig to those
in S0k;j=l for each x2Xj=l). In either case, S0i;j;k;l has a P4-decomposition (V(S0i;j;k;l);B0i;j;k;l)
by Lemma 3.1. Let B9 = Si;k2Zz;j;l2Z4;i6=korj6=lB0i;j;k;l.
(V(G);S1 i 9Bi) is a P4-decomposition of G = KG16w+16;2 .
It now remains to  nd a P4-decomposition of KGn;2 for each n2f16w+1;16w+2;16w+
3g. To construct these P4-decompositions, we will extend a P4-decomposition (T(Zn 1);B0)
of KGn 1;2 to a P4-decomposition of KGn;2. De ne   n 1(mod 16) with  2f0;1;2g.
Partition Zn 1 into 4w sets: Si =f4i;4i + 1;4i + 2;4i + 3g for i2Z4w 1 and S4w 1 =
Zn 1nZ16w 4. It is convenient to partition the vertices of the form T(Zn 1), into the following
two types:
Vi =ffx;ygjx;y2Si;x6= yg for i2Z4w, and
Vi;j =ffx;ygjx2Si;y2Sjg for 0 i<j < 4w.
Further, partition the vertices containing the new element n 1 into the 4w sets:
S0i =ffx;n 1gjx2Sig for each i2Z4w.
The subgraph of KGn;2 induced by vertices in T(Zn)nT(Zn 1) clearly has no edges, since
they all share the element n 1. All that needs to be shown is that the bipartite subgraph
28
G0 induced by the edges connecting verices in T(Zn 1) to vertices in T(Zn)nT(Zn 1) has a
P4-decomposition.
It will be helpful in the following discussion to de ne the following bipartite subgraphs
of G0:
Gi;j is the bipartite subgraph induced by the edges in ffx;ygjx2Vi;y2S0jg, and
Gi;j;k is the bipartite subgraph induced by the edges in ffx;ygjx2Vi;j;y2S0kg.
The following parts of the construction are identical for all  .
For each i;j2Z4w 1, consider Gi;j. If i6= j, then Gi;k is isomorphic to K6;4 and therefore
has a P4-decomposition (V(Gi;j);Bi;j) by Lemma 3.1. If i = j, then Gi;k is isomorphic to H1
and therefore has a P4-decomposition (V(Gi;j);Bi;j) by Lemma 3.2(i).
For eachi2Z4w 1, G4w 1;i is isomorphic toK(4+ 
2 );4
and therefore has aP4-decomposition
(V(G4w 1;i);B4w 1;i) by Lemma 3.1.
For 0  i < j < 4w 1 and k 2 Z4w 1, consider Gi;j;k. If k =2fi;jg, then Gi;j;k is
isomorphic to K16;4 and therefore has a P4-decomposition (V(Gi;j;k);Bi;j;k) by Lemma 3.1.
If k2fi;jg then without loss of generality assume that i = k. Then Gi;j;k consists of four
edge disjoint copies of K3;4 (induced by the edges connecting the vertices inffa;ygjy2Sjg
to those in S0i=k for each a2Si=k). Thus Gi;j;k has a P4-decomposition (V(Gi;j;k);Bi;j;k) by
Lemma 3.1.
For 0 i<j < 4w 1 and k = 4w 1, Gi;j;k is isomorphic to K16;4+ and thus has a
P4-decomposition (V(Gi;j;4w 1);Bi;j;4w 1) by Lemma 3.1.
The only edges remaining are those in Gi;4w 1 where i 2 Z4w and those in Gi;4w 1;k
where i2Z4w 1 and k2Z4w. The way these situations are treated depends on  .
First, suppose that  2f0;2g.
29
For each i2Z4w, consider Gi;4w 1. If i6= 4w 1 then Gi;4w 1 is isomorphic to K6;4+ 
and therefore has a P4-decomposition (V(Gi;4w 1);Bi;4w 1) by Lemma 3.1. If i = 4w 1
then Gi=4w 1;4w 1 is isomorphic to H1 if  = 0 and isomorphic to H2 if  = 2. In either case,
Gi=4w 1;4w 1 has a P4-decomposition (V(G4w 1;4w 1);B4w 1;4w 1) by Lemma 3.2(i) and (ii)
respectively.
Next, for each i2Z4w 1 and each k2Z4w, consider Gi;4w 1;k. If k =2fi;4w 1g then
Gi;4w 1;k is isomorphic toK4(4+ );4 and therefore has aP4-decomposition (V(Gi;4w 1;k);Bi;4w 1;k)
by Lemma 3.1. If k = i, then Gi;4w 1;k is the disjoint union of the graphs H3(ffa;n 1gja2
Sig;ffa;n 2jgja2Sig;ffa;n 2j 1gja2Sig) for each j2f1;2gif  = 0 and for each
j2f1;2;3gif  = 2. Each of these subgraphs has a P4-decomposition by Lemma 3.2(iii), so
their union forms a P4-decomposition (V(Gi;4w 1;k=i);Bi;4w 1;k=i) of Gi;4w 1;k=i. If k = 4w 1
then Gi;4w 1;k=4w 1 consists of 4 + edge disjoint copies of K4;3+ (induced by the edges con-
necting the vertices in ffx;agj x 2 Sig to those in S0k=4w 1 for each a 2 Sk=4w 1). So
Gi;4w 1;k=4w 1 has a P4-decomposition (V(Gi;4w 1;k);Bi;4w 1;k) by Lemma 3.1.
Let B1 = Si;j2ZtBi;j and B2 = S0 i<j t 1;k2ZtBi;j;k. The required P4-decomposition of
G is given by (V(G);Si2Z3 Bi).
Finally, suppose that  = 1.
For each j2Z2w, consider G0j = G2j;4w 1[G2j+1;4w 1. If j6= 2w 1, then G0j is isomor-
phic to K12;5 and therefore has a P4-decomposition (V(G0j);B0j;4w 1) by Lemma 3.1. If j =
2w 1, then G0j is isomorphic to H6 and therefore has a P4-decomposition (V(G0j);Bj;4w 1)
by Lemma 3.2(vi).
For each i 2 Z4w 1 and each k 2 Z4w, consider Gi;4w 1;k. If k =2fi;4w 1g, then
Gi;4w 1;k is isomorphic to K20;4 and therefore has a P4-decomposition (V(Gi;4w 1;k);Bi;4w 1;k)
by Lemma 3.1. If k = i, then Gi;4w 1;k is the disjoint union of the graphs H5(ffa;n 
1g j a 2 Sig;ffa;n 2g j a 2 Sig;ffa;n 3g j a 2 Sig;ffa;n 4g j a 2 Sig) and
H3(ffa;n 1gj a 2 Sig;ffa;n 5gj a 2 Sig;ffa;n 6gj a 2 Sig) and so has a P4-
decomposition (V(Gi;4w 1;k=i);Bi;4w 1;k=i) by Lemma 3.2 (v) and (iii). If k = 4w 1, then
30
Gi;4w 1;k=4w 1 consists of  ve edge disjoint copies of K4;4 (induced by the edges connecting
the vertices inffx;agjx2Sigto those in S0k=4w 1 for each a2Sk=4w 1). So Gi;4w 1;k=4w 1
has a P4-decomposition (V(Gi;4w 1;k);Bi;4w 1;k) by Lemma 3.1.
Let B1 = Si2Z4w;j2Z4w 1 Bi;j, B2 = Sj2Z2w B0j;4w 1 and
B3 = S0 i<j t 1;k2Z4w Bi;j;k. The requiredP4-decomposition ofGis given by (V(G);S0 i 3Bi).
31
Chapter 4
Embedding Partial P3-systems
4.1 Introduction
In this chapter, the problem of embedding maximal partial 3-path designs is completely
solved. Recall that the embedding problem is that for each partial H-design (V0;P0) of order
n,  nd the set of integers M such that m2M if and only if there exists an H-design (V;P)
of Km such that V0 V and P0 P. Recall also that the existence of P3-designs was settled
by Tarsi [28].
Theorem 4.1. There exists a Pm-design of order n if and only if n(n+1)2  0 (mod m) and
n m+ 1.
4.2 Building Blocks
In the discussion that follows we will use the following de nitions. A star of order k,
Sk, is the complete bipartite graph K1;k (possibly k = 0). The vertex c(Sk) of Sk with
degree k when k  2 is said to be the center of Sk; if k = 1 then either vertex can be
designated to be the center. The leave of a partial H-design (V;P) of order n is the graph
L = (V(Kn);E(Kn)nE(P)). A partial H-design is said to be maximal if its leave has no
proper subgraphs isomorphic to H. Let (a;b;c;d) denote the path, P3, of length three with
edge set ffa;bg;fb;cg;fc;dgg. The disjoint union of two graphs G and H, denoted G+H,
is the graph with vertex set V(G)[V(H) and edge set E(G)[E(H).
The Billington and Ho man result [5] will be very useful in the constructions to come:
Lemma 4.1. The complete bipartite graph Ka1;a2 with a1  a2 has a P3-decomposition if
and only if a1  2, a2  3 and a1a2  0 (mod 3).
32
The following lemmas will be useful in the constructions to come.
Lemma 4.2. There exists a P3-decomposition of the following graphs:
(i) H1 = (S3_KC2 ) F where F =ffx;c(S3)gjx2V(KC2 )g,
(ii) H2 = (S3_KC3 ) F where F =ffx;c(S3)gjx2V(KC3 )g,
(iii) H3 = (S3_KC4 ) F where F =ffx;c(S3)gjx2V(KC4 )g,
(iv) H4 = ((S2 +S1)_KC2 ) F where F =ffx;cgjx2V(KC2 );c2fc(S2);c(S1)gg,
(v) H5 = ((S2 +S1)_KC3 ) F where F =ffx;cgjx2V(KC3 );c2fc(S2);c(S1)gg,
(vi) H6 = ((S2 +S1)_KC4 ) F where F =ffx;cgjx2V(KC4 );c2fc(S2);c(S1)gg, and
(vii) H7 = S1_KC4 .
Proof. For each of the following, let V(KCn ) =fv1;v2;:::;vng, V(S3) =fc;a1;a2;a3g where
c is the center, V(S2) =fc2;a1;a2g and V(S1) =fc1;b1g where c2 and c1 are the centers of
S2 and S1 respectively.
(i) (V(H1);f(c;a3;v1;a2);(a1;c;a2;v2);(a3;v2;a1;v1)g) is the desired decomposition.
(ii-iii) Let n2f2;3g. The subgraph of Hn obtained by removing the edges in the two three
paths (c;a1;v1;a2) and (a2;c;a3;v1) is isomorphic to Kn;3, so has a P3-decomposition
(V(Hn);Bn) by Lemma 4.1. Then (V(Hn);Bn[f(c;a1;v1;a2);(a2;c;a3;v1)g) gives the
desired decomposition.
(iv) (V(H4);f(c1;b1;v1;a2);(a1;c2;a2;v2);(b1;v2;a1;v1)g) is the desired decomposition.
(v-vi) Let n 2 f5;6g. The subgraph of Hn obtained by removing the edges in the two
three paths (c1;b1;v1;a1) and (a1;c2;a2;v1) is isomorphic to Kn 3;3, so has a P3-
decomposition (V(Hn);Bn) by Lemma 4.1. Then (V(Hn);Bn[f(c1;b1;v1;a1);(a1;c2;a2;v1)g)
gives the desired decomposition.
33
(vii) (V(H7);f(v1;c1;b1;v4);(v1;b1;v2;c1);(v4;c1;v3;b1)g is the desired decomposition.
Lemma 4.3. There exists a P3-decomposition of the following graphs:
(i) G1 = ((S1 +S1 +S1)_KC2 ),
(ii) G2 = ((S1 +S1 +S1)_KC3 ), and
(iii) G3 = ((S1 +S1 +S1)_KC4 ).
Proof. For each of the following, let V(KCn ) =fv1;v2;:::;vngand let the vertex sets for the
three one stars be fa1;a2g, fb1;b2g, and fc1;c2g.
(i) (V(G1);f(a1;a2;v1;b1);(b1;b2;v2;a2);(b1;v2;c1;c2);(b2;v1;a1;v2);
(v2;c2;v1;c1)g) is the required decomposition.
(ii-iii) Let n 2f2;3g. The subgraph of Gn obtained by removing the edges in the three
three paths (a1;a2;v1;b1);(b1;b2;v1;c1); and (c1;c2;v1;a1) is isomorphic to Kn;6, so has
a P3-decomposition (V(Gn);Bn) by Lemma 4.1. Then (V(Gn);Bn[f(a1;a2;v1;b1);
(b1;b2;v1;c1);(c1;c2;v1;a1)g) gives the desired decomposition.
Lemma 4.4. There exists a P3-decomposition of K4.
Proof. Let V(K4) = Z4. Then (V(K4);f(0;1;2;3);(0;2;1;3)gis the required decomposition.
Lemma 4.5. There exists a P3-decomposition of K3_KCm for all m 1.
Proof. Let V(K3) =fa;b;cg and V(KCm) = Zm. For m = 1, the graph is isomorphic to K4
and has a P3-decomposition by Lemma 4.4. For m = 2, (V(KC2 );f(1;a;c;2);
(a;b;1;c);(c;b;2;a)g) is the required decomposition. For m 3, consider the subgraph G
of K3 _KCm induced by the vertices in fa;b;c;1g. G is isomorphic to K4, and has a P3-
decomposition by Lemma 4.4. The remaining edges in (K3_KCm) G are isomorphic to
K3;m 1 and have a P3-decomposition by Lemma 4.1. The union of these decompositions give
the required decomposition.
34
4.3 Embedding Partial P3-designs.
We now prove the main results.
Theorem 4.2. Let k  n + 2. A partial P3-design of order n 2 can be embedded in a
P3-design of order k if and only if k 0 or 1 (mod 3) and k 4.
Proof. Suppose there exists a P3-design of order k. Then it must be the case that the number
of edges in Kk is a multiple of three. This occurs when k 0 or 1 (mod 3). Further, since
K3 has no P3-design, it must be the case that k 4. So the necessity is proved.
To prove the su ciency,  rst note that if n 2 then the result follows from Theorem 4.1,
so assume that n 3. Begin by adding copies of P3 to the given partial P3-design until a
maximal partial P3-design (V;B) of order n is obtained. The result will follow once it is
shown that (V;B) can be embedded in P3-designs of orders n + 3 and n + 4 when n 0
(mod 3), orders n + 2 and n + 3 when n 1 (mod 3), and order n + 2 when n 2 (mod
3), since the embedding for all values larger than these can be obtained through repeated
application of these small embeddings.
Since (V;B) is a maximal partial P3-design, each component of its leave, L, must be a
K3 or a star (possibly with no edges), for otherwise it would contain a path of length three.
Let T =fT1;T2;:::;Ttgbe the set of components of L which are isomorphic to K3, let P be
the subgraph of L consisting of the components isomorphic to Si with i 2, let R be the
subgraph of L consisting of components that are isomorphic to S1 = K2, and I be the set of
isolated vertices in L (copies of S0).
Let m2f2;3;4gsuch that n+m 0 or 1 (mod 3). Construct a P3-design (V[V0;B0)
of order n+m with B B0 as follows.
For each 1 i t, the subgraph T0i of Kn+m induced by the edges in E(Ti)[ffx;ygj
x2V(Ti);y2V0g is isomorphic to K3_KCm and has a P3-decomposition (V(T0i);BTi) by
Lemma 4.5. Let BT = S1 i tBTi.
35
Let fRi j 1  i  djE(R)j=3eg be a partition of E(R) with jRij = 3 for each i  
jE(R)j=3. For each i jE(R)j=3, the subgraph of Kn+m induced by the edges in E(Ri)[
ffx;ygjx2V(Ri);y2V0gis isomorphic to (S1 +S1 +S1)_KCm, so has a P3-decomposition
(V(Ri);BRi) by Lemma 4.3. Let BR = S1 i jE(R)j=3BRi. If jE(R)j 1 or 2 (mod 3), then
the subgraph induced by RdjE(R)j=3e is isomorphic to S1 or (S1 + S1) respectively; the edges
in these subgraphs have not yet been placed into 3-paths.
Let C1;C2;:::;Cl be the components of P. LetfPij1 i djE(P)j=3egbe a partition
of E(P) withjPij= 3 for each i jE(P)j=3 such that for all i<j, if e1 2(Pi\E(Ck)) and
e2 2(Pj\E(Cl)) then k l. This partion ensures that for each i jE(P)j=3, Pi induces a
subgraph of L isomorphic to either S3 or (S2 + S1), and that PdjE(P)j=3e induces a subgraph
of L isomorphic to S1 if jE(P)j 1 (mod 3) and to S2 if jE(P)j 2 (mod 3). For each
i jE(P)j=3, let C0i be the collection of centers of any stars of P with edges in Pi and consider
the subgraph of Kn+m induced by the edges in E(Pi)[ffx;ygjx2V(Pi)nC0i;y2V0g. This
subgraph is isomorphic to either (S3_KCm) F or ((S2+S1)_KCm) F as de ned in Lemma 4.2
and thus has a P3-decomposition (V(Pi);BPi) by Lemma 4.2. Let BP = S1 i jE(P)j=3BPi.
Note that we have now placed all edges in L into paths of length three except for those
in RdjE(R)j=3e and PdjE(P)j=3e whenever jE(R)j and jE(P)j respectively is not a multiple of
three. At this point, the edges between 3(bjE(P)j=3c+bjE(R)j=3c+jTj) vertices in L and
each of the vertices in V0 now occur in 3-paths. We now consider two cases in turn.
First, suppose that n  0 or 1 (mod 3), then jE(L)j  0 (mod 3). Therefore, if
the number of edges in either R or P is not divisible by 3, then the subgraph induced by
RdjE(R)j=3e[PdjE(P)j=3e is isomorphic either to (S2 + S1) or (S1 + S1 + S1). If RdjE(R)j=3e[
PdjE(P)j=3e is isomorphic to (S2 + S1) then the subgraph of Kn+m induced by the edges in
E(RdjE(R)j=3e[PdjE(P)j=3e)[ffx;ygjx2V(RdjE(R)j=3e[PdjE(P)j=3e)nC0;y2V0g (where C0 is
the set of centers of the two stars in question) is isomorphic to ((S2+S1)_KCm) F as de ned
in Lemma 4.2 and thus has a P3-decomposition (V(RdjE(R)j=3e[PdjE(P)j=3e);B ) by Lemma 4.2.
If RdjE(R)j=3e[PdjE(P)j=3e is isomorphic to (S1 +S1 +S1), then the subgraph of Kn+m induced
36
by the edges in E(RdjE(R)j=3e[PdjE(P)j=3e)[ffx;ygjx2V(RdjE(R)j=3e[PdjE(P)j=3e);y2V0gis
isomorphic to (S1+S1+S1)_KCm and has a P3-decomposition (V(RdjE(R)j=3e[PdjE(P)j=3e);B )
by Lemma 4.3 (let C0 =; in this case). Note that all edges in L have now been placed into
paths of length three.
All that remains when n 0 or 1 (mod 3) is to place the edges connecting the vertices
in I0 = I[C0[fSi jE(P)j=3C0igto the vertices in V0 and the edges in the subgraph of Kn+m
induced by the vertices in V0 into paths of length three. Note that: exactly three vertices in
V(Pi) have all of the edges connecting them to the vertices in V0 placed into paths of length
three in BPi; all six vertices in V(Ri) have all of the edges connecting them to the vertices
in V0 placed into paths of length three in BRi; and all three vertices in V(Ti) have all of
the edges connecting them to the vertices in V0 placed into paths of length three BTi. This
immediately implies that jI0j n (mod 3).
If n 0 (mod 3), then the bipartite subgraph induced by the edgesffx;ygjx2I0;y2
V0g is isomorphic to KjI0j;m and has a P3-decomposition (I0;BI) by Lemma 4.1. Note that
all the subconstructions used so far have at least one path either of the form p1 = (a;u;b;v)
or p2 = (a;b;u;c) where fa;b;cg2V(L) and fu;vg2V0. If m = 3, either replace p1 with
the paths (a;u;v;w) and (w;u;b;v) or replace p2 with the paths (c;u;v;w) and (w;u;b;a),
thereby placing edges joining vertices in V0 into 3-paths. If m = 4, then by Lemma 4.4, let
(V0;BN) be a P3-design of order 4. The union of all 3-paths thus de ned completes the case
where n 0 (mod 3).
If n  1 (mod 3), then m 2f2;3g and jI0j 1 (mod 3). Again, note that all the
subconstructions used so far have at least one path either of the form p1 = (a;u;b;v) or
p2 = (a;b;u;c) where fa;b;cg2V(L) and fu;vg2V0. If V(I0) = fwg and m = 2, then
replace p1 with the paths (a;u;v;w) and (w;u;b;v), or replace p2 with the paths (c;u;v;w)
and (w;u;b;a). If V(I0) = fwg and m = 3, then by Lemma 4.4, let (V0[fwg;BN) be a
P3-design of order 4. If jI0j 4 and m = 2, then partition I0 into two sets I01 and I02 with
jI01j= 4 and jI02j=jI0j 4 0 (mod 3). The subgraph of Kn+m induced by the vertices in
37
V0[I01 is isomorphic to H7 and has a P3-decomposition (V0[I01;BN) by Lemma 4.2. The
bipartite subgraph induced by the edges ffx;ygjx2I02;y2V0g is isomorphic to KjI0j 4;2
and has a P3-decomposition (V0[I02;BI) by Lemma 4.1. If jI0j 4 and m = 3, then let
a2I0. The subgraph of Kn+m induced by the vertices in V0[fag is isomorphic to K4 and
has a P3-decomposition (V0[fag;BN) by Lemma 4.4. The remaining edges, namely those
in ffx;ygjx2I0nfag;y2V0g, induce a bipartite subgraph isomorphic to KjI0j 1;3 and has
a P3-decomposition (V0[I0nfag;BI) by Lemma 4.1. The union of all 3-paths thus de ned
completes the case where n 1 (mod 3).
Finally consider the case where n  2 (mod 3), so m = 2. In this case jE(L)j 
1 (mod 3), so there must be exactly 1 or 4 edges in RdjE(R)j=3e[PdjE(P)j=3e. Therefore,
RdjE(R)j=3e[PdjE(P)j=3e must induce a graph isomorphic to S1 or to (S2 +S1 +S1) (note that
RdjE(R)j=3e[PdjE(P)j=3e can?t induce a subgraph isomorphic to S2 +S2, since PdjE(P)j=3e induces
a subgraph isomorphic to either S1 or S2 and RdjE(R)j=3e induces a subgraph isomorphic to
either S1 or S1 +S1).
If RdjE(R)j=3e[PdjE(P)j=3e induces a graph isomorphic to S1, then the subgraph of Kn+2
induced by the vertices in V0[RdjE(R)j=3e[PdjE(P)j=3e is isomorphic to K4 and has a P3-
decomposition (V0[RdjE(R)j=3e[PdjE(P)j=3e;BN) by Lemma 4.4. This leaves the edges con-
necting the vertices in V0 to those in I00 = I[fSi jE(P)j=3C0ig. Note that since RdjE(R)j=3e[
PdjE(P)j=3e induces a graph on exactly two vertices, jI00j 0 (mod 3). Thus the bipartite
subgraph induced by the edges ffx;ygjx2I00;y 2V0g is isomorphic to KjI0j;2, so has a
P3-decomposition (V0[I00;BI) by Lemma 4.1.
If RdjE(R)j=3e[PdjE(P)j=3e induces a graph isomorphic to (S2 +S1 +S1), then partition the
edges in RdjE(R)j=3e[PdjE(P)j=3e into P01 and P02 such that P01 induces a subgraph isomorphic
to (S2 + S1) and P02 induces a subgraph isomorphic to S1. Consider the the subgraph of
Kn+m induced by the edges in E(P01)[ffx;ygjx2V(P01)nC0;y2V0gwhere C0 is the set of
centers of the two stars in P01. This subgraph is isomorphic to ((S2 +S1)_KCm) F as de ned
in Lemma 4.2 and thus has a P3-decomposition (V(P01);B ) by Lemma 4.2. The subgraph of
38
Kn+2 induced by the vertices in V0[P02 is isomorphic to K4 and has a P3-decomposition by
Lemma 4.4. This leaves the bipartite subgraph induced by the edgesffx;ygjx2I0;y2V0g
with I0 as de ned above. This subgraph is isomorphic to KjI0j;2, so has a P3-decomposition
(V0[I0;BI) by Lemma 4.1.
Let B0 = B[BT [BR[BP [BN[BI[B . Then (V(Kn+m;B0) is an embedding of
(V(Kn;B) as required.
Theorem 4.3. A maximal partial P3-design (V;B) of order n can be embedded in a P3-design
of order n+ 1 if and only if
(i) n 0 or 2 (mod 3),
(ii) jE(L)j n=2, and
(iii) n6= 2
Proof. To prove the necessity, assume that (V;B) is embedded in a P3-design (V [fvg;B0)
of order n + 1. By Theorem 4.1, n + 1  0 or 1 (mod 3), so n 0 or 2 (mod 3). Clearly
n6= 2 since by Theorem 4.1 there is no P3-design of order 3. To show the necessity of the
condition jE(L)j n=2, note that since (V;B) is maximal, each new 3-path in B0nB must
either be of the form (a;b;c;v) using two edges of L or (a;b;v;c) using one edge in L, where
fa;b;cg2V(L). De ne paths of the  rst form as Type 1 and of the second as Type 2. Let
x be the number of paths of Type 1 in any embedding and let y be the number of paths of
Type 2. By considering the edges in L in paths in B0nB it follows that 2x + y = jE(L)j.
Also, the n edges joining vertices in L to v are all in paths in BnB0, so x+2y = n. Therefore
x = (2jE(L)j n)=3 and y = (2n jE(L)j)=3. Since x must be a nonnegative integer,
jE(L)j n=2. (Note that y  0 implies that jE(L)j 2n. But since each component
in each maximal P3-design is K3 or a star, in fact jE(L)j n, so this apparent necessary
condition is always satis ed.)
To show the su ciency, we will embed a maximal partial P3-design (V;B) of order n
satisfying the necessary conditions into a P3-design (V[fvg;B0) of order n+1. If n = 3 then
39
L = K3 so the result follows from Theorem 4.1, so we can assume that n 5. Recall that
in the leave L of any maximal partial P3-designs, each component must be a K3 or a star
(possibly with no edges), otherwise it would contain a path of length three. In particular,
this means that jE(L)j n.
As is shown above, we must construct x = (2jE(L)j n)=3 3-paths of Type 1 and
y = (2n jE(L)j)=3 3-paths of Type 2. Note that since jE(L)j n, y (2n n)=3 5=3
so y  2. To be able to construct x 3-paths of Type 1, clearly there must be at least x
edge-disjoint 2-paths in L. To show that there are su ciently many 2-paths in L to use as
building blocks for the Type 1 paths, consider the value 2jE(L)j n. Let L0 be the subgraph
of L induced by the components of L not isomorphic to S0 or S1. Since each component
of L isomorphic to S0 has one vertex and zero edges and each component of L isomorphic
to S1 has two vertices and one edges, it follows that n jV(L0)j 2(jE(L)j jE(L0)j), so
2jE(L0)j jV(L0)j 2jE(L)j n. Now consider a maximal P2-decomposition (V(L0);D)
of the subgraph induced by L0. Since D contains exactly two edges in each component
isomorphic to K3 and contains all of the edges of each component that is a star except
possibly one, it follows that the number of edges in D is at least two thirds of the total
number of edges in L0; sojDj jE(L0)j=3. Also note thatjE(L0)j jV(L0)jsince L0 consists
entirely of disjoint stars and K03s, so jE(L0)j 2jE(L0)j jV(L0)j. So jDj jE(L0)j=3  
(2jE(L0)j jV(L0)j)=3  (2jE(L)j n)=3 = x, ensuring that there are indeed at least x
2-paths in L.
Construct the Type 1 3-paths as follows. LetfX0iji2Zxgbe any set of x edge disjoint
paths of length two in L. For each i2Zx, extend X0i = (a;b;d) to the 3-path Xi = (a;b;d;v).
Let X =fXiji2Zxg. Note that because each component of L is a K3 or a star,
(1) for each edgefa;bgin L that occurs in no 3-path in X, at least one of the edgesfa;vg
and fb;vg does not occur in a 3-path in X.
Also note that if c is the center of a star then the edge of the formfc;vghas not been placed
into a 3-path in X, since no center can be an end of a 2-path in L.
40
Let Y00 =fY00i ji2Zyg be the subset of E(L) consisting of the jE(L)j 2x = y edges
not occurring in paths in X. Finally we show how to place into 3-paths the edges in Y00
together with the edges in the set W consisting of the n x = 2y edges incident with v that
occur in no 3-path in X. It is easy to direct the edges in Y00 so that in the resulting directed
graph D:
(i) if (a;b) is the arc in D corresponding to Y00i = fa;bg then fb;vg occurs in no path in
X (this is possible by (1)),
(ii) each vertex in D has in-degree at most 1, and
(iii) each center c of each star incident with an edge in Y00 has in-degree exactly 1.
Note that since each component of L is a K3 or a star, by (ii) it follows that:
(iv) the only vertices with out-degree greater than 1 are centers of stars.
For each i 2 Zy, if Y00i = fa;bg corresponds to (a;b) in D then de ne the 2-path
Y0i = (a;b;v); name these so that if b is the center of a star, then i is as small as possible.
More formally, if (a1;b1) and (a2;b2) are arcs in D corresponding to Y00i and Y00j respectively
and if b1 is the center of a star and b2 is not the center of a star, then i<j. Let Y0 = Si2Zy Y0i .
Let Z be the set consisting of the y edges in W occurring in no path in Y0. Then Z can
be partitioned into sets Z1 and Z2 where Z1 =ffu;vgj(u;c)2D, c is the center of a star
in Lg. By (iii) at most one vertex (namely v) is incident with more than one edge in Z1, so
we can name the vertices in D so that Z1 = ffui;vgji2ZjZ1jg where for each i2ZjZ1j,
(ui;ci) is the arc in D corresponding to Y00i , and ci is the center of a star in L. Then we can
let Z2 = ffui;vgji2ZynZjZ1jg. It turns out that the vertices in fui ji2ZynZjZ1jg are
isolated vertices in D. To see this, notice that if u2fuiji2ZynZjZ1jg, then:
(i) u is an isolated vertex in L, or
(ii) u appears in a 3-path in X of the form (a;u;b;v) where fa;ug and fu;bg are edges in
a component of L isomorphic to K3, or
41
(iii) u appears in a 3-path in X of the form (u;c;a;v) where fc;ug and fc;ag are edges in
a component of L isomorphic to a star with center c, or
(iv) u is the center or a star in L all of whose edges appear in 3-paths in X.
For each i 2 Zy, extend Y0i = (a;b;v) = (ui;b;v) to the 3-path Yi = (ui;b;v;ui+1)
reducing the sum modulo y. Let Y =fYiji2Zyg. Note that each element in Y is a 3-path,
since ui6= ui+1 since y 2.
All edges have now been placed into 3-paths, so (V(L)[fvg;B[X[Y) embeds (V;B)
into a complete P3-design of order n+ 1 as desired.
4.4 Further Comments
It is natural to consider embeddings of all partial P3-designs, not just maximal ones.
While Theorem 4.2 does  nd embeddings for all partial P3-designs, Theorem 4.3 does not.
The di culty when embedding partial P3-designs of order n into P3-designs of order
n + 1 arises because of condition (ii) in Theorem 4.3. Indeed, it is easy to  nd partial
P3-designs of order n that can be embedded in a P3-design of order n + 1, but can also be
extended to a maximal partial P3-design which cannot be embedded in a P3-design of order
n+ 1. As an example, consider the partial P3-design (V;B) of order 6 in which B is empty
(the leave is K6 itself). This can easily be embedded in a P3-designs of order 7 by Tarsi?s
result in [28], since any P3-design of order 7 embeds (V;B). (V;B) can be extended to a
maximal partial P3-design (V;B0) in which the leave is empty ((V;B0) is a complete design).
By Theorem 4.3, (V;B0) cannot be embedded in a P3-designs of order 7.
It is clear that new necessary conditions must be introduced to completely solve this
problem.
42
Chapter 5
Future Directions
Identifying and classifying underlying structures and decompositions of Kneser and Gen-
eralized Kneser Graphs seems to a be a fertile area for future results. In particular, the (Gen-
eralzed) Kneser Graphs have very strong underlying recursive structures that lend themselves
readily to inductive design constructions. As an example of this, consider the Kneser Graph
G = KGn;k on element set Zn. For any element i in the element set, the subgraph Gi of G
induced by the vertices not containing the element i is clearly isomorphic to KGn 1;k on the
element set Znnfig. Note that the collection of vertices in G containing the element i is an
independent set (no two are adjacent). This set is denoted Vi. G can therefore be viewed
as the edge-disjoint union of Gi and the bipartite subgraph Bi of G induced by the edges
ffa;bgja2V(Gi);b2Vig. So in this case, if we have some H-decomposition of Gi, and we
can  nd an H-decomposition of Bi, we immediately have an H-decomposition of G. Note
that Bi is not only bipartite, but any two vertices in a given partition have the same degree
in Bi. Graph decompositions of bipartite graphs have been well studied in the literature and
give a  rm grounding for these types of constructions (see for example [5]).
This approach not only allows one to show the existence of a given decomposition, but
actually creates a structure for building explicit constructions inductively. It can also be
generalized fairly readily to Generalized Kneser Graphs and illustrates the interrelationship
between Kneser Graphs and Generalized Kneser Graphs. To illustrate this, consider the
Generalized Kneser Graph G = GKGn;k;r on element set Zn. The subgraph G0i of G induced
by the vertices containing the element i is isomorphic to GKGn 1;k 1;r 1 on the element
set Znnfig. The subgraph Gi of G induced by the vertices not containing the element i
is isomorphic to GKGn 1;k;r on the element set Znnfig. G can therefore be viewed as the
43
edge-disjoint union of Gi, G0i and the bipartite subgraph Bi of G induced by the edges
ffa;bgja2V(Gi);b2V(G0i)g, with similar possibilities for analysis as above. Note that
the Kneser Graph is a Generalized Kneser Graph with r = 0, so repeated applications of
this procedure can partially reduce the task of decomposition of Generalized Kneser Graphs
to the decompositions of the Kneser Graph.
In each of the results discussed in Chapter 2, the obvious necessary condition that the
number of edges in the graph be a multiple of the path length turned out to also be su cient
for the existence of the relevant path decomposition. This, plus another small observation,
leads to the following conjecture.
Conjecture 1. The Kneser Graph KGn;k has a Pl-decomposition if and only if:
(i) n> 2k,
(ii) lj nk  n kk  =2 =jE(KGn;k)j,
(iii) and 2o(KGn;k)  jE(KGn;k)j=l where o(G) denotes the number of vertices in G with
odd degree.
The  rst two conditions simply ensure that the graph is connected and has a number of
edges that is a multiple of the path length. The connectivity is important, since if n = 2k,
then the graph is a 1-factor and if n< 2k, the graph has no edges The third condition comes
from the observation that removing a path from a graph will change the parity of exactly two
vertices in the graph (the endpoints of the path). If the number of paths in a proposed path
decomposition of a graph is less than half the number of odd vertices, then the proposed
path decomposition is clearly impossible, since a decomposition can be thought of as a way
to remove all edges from a graph, leaving each vertex with degree zero. There would be an
insu cient number of paths to turn all of the odd vertices to the even even zero. If this
conjecture can be established, it should be possible to extend the result to a similar result
for Generalized Kneser Graphs using the observations of the recursive nature of these graphs
discussed above.
44
Bibliography
[1] B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn I. J. Combin.
Theory Ser. B 81 (1) (2001), 77-99.
[2] L. D. Andersen, A. J. W. Hilton, and E. Mendelsohn, Embedding partial
Steiner triple systems. Proc London Math Soc 41 (3), (1980), 557-576.
[3] A. Bahmanian and C. A. Rodger, Multiply Balanced Edge Colorings of Multigraphs.
J. Graph Theory, to appear.
[4] I. B ar any, A short proof of Kneser?s conjecture. J. Combin. Theory Ser. A 25 (3),
(1978), 325 - 326.
[5] Elizabeth J. Billington and D. G. Hoffman, Short path decompositions of arbi-
trary complete multipartite graphs. Proceedings of the Thirty-Eighth Southeastern Inter-
national Conference on Combinatorics, Graph Theory and Computing. Congr. Numer.
187, (2007), 161-173.
[6] D. Bryant, Embeddings of partial Steiner triple systems. J Combin Theory Ser A 106,
(2004), 77-108.
[7] Darryn Bryant and Daniel Horsly, A proof of Lindner?s conjecture on embeddings
of partial Steiner triple systems. J. Combin. Des. 17 (1), (2009), 63-89.
[8] Y. Chen, Kneser graphs are Hamiltonian for n 3k. J. Combin. Theory Ser. B 80(1),
(2000), 69 - 79.
[9] Dalibor Froncek, Cyclic decompositions of complete graphs into spanning trees. Dis-
cuss. Math. Graph Theory 24(2), (2004), 345 - 353.
[10] H. L. Fu and C. A. Rodger, Group divisible designs with two associate classes: n
= 2 or m = 2. J. Combin. Theory Ser. A 83 (1998), 94 - 117.
[11] H. L. Fu and C. A. Rodger, 4-cycle group divisible designs with two associate classes.
Combin. Probab. Comput. 10 (2001), 317-343.
[12] J. E. Greene, A new short proof of Kneser?s conjecture. Amer. Math. Monthly 109
(10), (2002), 918 - 920.
[13] Terry S. Griggs, Steiner triple systems and their close relatives. Quasigroups Related
Systems 19 (1), (2011), 23 - 68.
45
[14] D. G. Hoffman, C. C. Lindner, and C. A. Rodger, On the construction of odd
cycle systems. J. Graph Theory 13 (4), (1989), 417 - 426.
[15] Lijun Ji, Existence of Steiner quadruple systems with a spanning block design. Discrete
Math. 312 (5), (2012), 920-932.
[16] T. P. Kirkman, On a problem in combinations. Cambridge Dublin Math J 2 (1847),
191-204.
[17] M. Kneser, Aufgabe 360. Jahresbericht der Deutschen Mathematiker-Vereinigung, 2.
Abteilung 58, (1955), 27.
[18] Anton Kocig (Anton K otzig), Decomposition of a complete graph into 4k-gons.
Mat.  Casopis Sloven. Akad. Vied 17, (1967), 229-233.
[19] C. C. Lindner, A partial Steiner triple system of order n can be embedded in a Steiner
triple system of order 6n+ 3. J Combin Theory Ser A 18, (1975), 349-351.
[20] C. C. Lindner and T. Evans, Finite embedding theorems for partial designs and
algebras. S eminaire de Math ematiques Sup erieures 56 ( Et e 1971), Les Presses de
l?Universit e de Montr eal, Montreal, Que., (1977), 196 pp.
[21] L. Lov asz, Kneser?s conjecture, chromatic number, and homotopy. J. Combin. Theory
Ser. A 25 (3), (1978), 319 - 324.
[22] J. Matou sek, A combinatorial proof of Kneser?s conjecture. Combinatorica 24 (1),
(2004), 163 - 170.
[23] Alexander Rosa, On cyclic decompositions of the complete graph into (4m+2)-gons.
Mat.-Fyz.  Casopis Sloven. Akad. Vied 16, (1966), 349-352.
[24] Mateja  Sajna, On decomposing Kn I into cycles of a  xed odd length. Algebraic
and topological methods in graph theory (Lake Bled, 1999). Discrete Math. 244 (1-3)
(2002), 435-444.
[25] Ian Shields and Carla D. Savage, A note on Hamilton cycles in Kneser graphs.
Bull. Inst. Combin. Appl. 40, (2004), 13 - 22.
[26] D. Sotteau, Decomposition of Km;n(K m;n) into cycles (circuits) of length 2k. J. Com-
bin. Theory Ser. B 30 (1), (1981), 75-81.
[27] Michael Tarsi, On the decomposition of a graph into stars., Discrete Math. 36 (1981),
299-304.
[28] Michael Tarsi, Decomposition of a complete multigraph into simple paths: nonbal-
anced handcu ed designs., Journal of Combinatorial Theory, Series A 34 (1) (1983),
60-70.
46