MA5221 and MA6280: Graph Decomposition
Course description
- Subject:
-
The subject this year for the MA5221 Graph Theory will be graph
decomposition. Students may also take this course as credit for
MA6280 by giving an oral presentation in the
Combinatorics seminar on a course related topic.
This can be either your original research or on an approved
reading.
- Content:
-
This course will survey the classical problems of decomposing
the edges set of a graph into subgraphs. For example if
X is a graph and G is a subgraph of X a G-decomposition of X is a partition of the edges of X into subgraphs isomorphic to G. It is my hope that this will provide a rich source of student research topics. Topics may include.
- The Walecki decomposition:
-
one-factorizations and
Near-one-factorizations.
- Ringle's problem:
-
For each tree T, |T|=n find a T-decomposition of
K2n+1.
- The graceful labeling problem:
-
Let G be a graph with e edges.
A graceful labeling of G is
is a one-to-one mapping
h:V(G)→ {0,1,2,…,e} such that
the induced edge labeling
{|h(x)−h(y)| : xy ∈ E(G)} = {1,2,3,…,e}.
Then developing this G (labeled by h) modulo n=2e+1
will decompose Kn into subgraphs isomorphic to G.
- Kotzig's problem
-
Let Ti, i=1,2,…,n be a list of trees where
|Ti|=i. Can you decompose Kn+1
into these trees (each exactly once.)
- Nash Williams' problem.
-
If G is a graph with all degrees even having 3t edges
and MinDeg(G) ≥ 3n/4, can G be decomposed into t
triangles? Such a decomposition is called a partial Steiner triple system.
- The Oberwolfach problem (Ringle 1967):
-
Let G be a 2-regular graph of order n.
When does Kn have a G-decomposition.
- Hamilton-Waterloo problem:
-
Determine the existence of a 2-factorization
of K2n+1 in which r of the 2-factors are
isomorphic to a given 2-factor R and s of the
2-factors are isomorphic to a given 2-factor S , with r + s = n.
- Alspach conjecture on cycles:
-
Let Ci, i=1,2,... be a list of cycles.
If ∑i |Ci| = n(n−1)/2 when n is odd and
n(n−2)/2 when n is even, can you decompose Kn or Kn−I into these types of cycles.
- Kelly's question:
-
Can any regular tournament be decomposed
into Hamilton directed cycles.
- Alspach's conjecture:
-
Every Cayley graph on an abelian group has
a Hamilton decomposition.
Required text
There is no required text for this course, so we will write
our own. Indeed there is no affordable textbook on the market.
Non-required text
A non-required book on general graph theory is:
J.A. Bondy and U.S.R. Murty, Graph Theory,
Graduate Text in Mathematics 244, Springer, 2008.
You do not need to buy this book. But it is not expensive
and is available from our book store. You can get it cheaper
(under $50) by ordering online. For example search amazon.com with keyword "bondy murty". It is a good book and the one I would choose for a general graph theory course. I highly recommend it.
You can also buy my book:
W. Kocay and D.L. Kreher, Graphs, Algorithms, and Optimization , Chapman & Hall/CRC Press , Boca Raton, Florida, 2005
for a more algorithmic approach to graph theory.
Background and prerequisites
I will assume no background. We will start with basic definitions of graph theory, but focus on the problems of graph decomposition.
Grading
Your grade will be based on homework assignments and midterm examinations. If you enroll as an advanced student for MA6280 you will be expected to give a seminar presentation.