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 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 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