Dear Colleagues,

We continue our Colloquium in the Math Department.

*************************

Speaker: David Ashe, Department of Mathematics, University of Tennessee
at Chattanooga

Time/Place: Wednesday, March 2, 2:00 pm, EMCS 233.

Title: Graph Decompositions

Abstract:
Theorem: Let R be a disjoint 2-regular subgraph in the complete graph
K_n. There exists a 8-cycle system of G = K_n - E(R) where E(R) are the
edges in R if and only if:
1) all vertices in R have even degree,
2) |E(K_n - E(R))| is divisible by 8, and
3) n is odd.

Showing that the 3 conditions are necessary is straight forward, however
showing that they are sufficient is more involved. The approach taken is
inductive. The following Lemma is required.

Lemma: Let n be odd and let R be a 2-regular subgraph of the complete
graph K_n. The number of edges in K_n - E(R) where E(R) is the number of
edges in R is divisible by 8 if and only if n and I(R) where I(R) is the
number of vertices not in R (isolated vertices) are related as shown
below.

n(mod 16)      1   3   5   7   9  11  13  15
I(R)(mod 8)    1   0   3   2   5   4   7   6

Vertices are selected wisely and partitioned from K_n such that I(R) and
the number of vertices remaining in this modified graph call it H fall
into the same category in the table above. The lemma is then used to
show the number of edges in H and not in R are divisible by 8 and can be
partitioned into 8-cycles.

The next step is to partition the edges incident with H and incident
with the removed vertices from K_n (those not in H) into 8-cycles.
Sotteau's theorem accomplishes this. There is a more general version. It
is stated here for 8-cycles specifically.

Sotteau's Theorem: There exists a 8-cycle system of K_{a,b} if and only
if:
1) a and b are even
2) 8 divides a or b, and
3) minimum {a, b} > 4.

Unfortunately, Sotteau's theorem does not partition all of the remaining
edges into 8-cycles. They have to be found by hand, trial and error,
brute force, etc. In actuality, these 8-cycles (the widget) must be
found first keeping in mind that Sotteau's theorem and the lemma will be
used later.

This is a general summary of the proof, however there are many cases
that had to be considered and this process was applied to each of them.

--
John V. Matthews, III      \ http://www.utc.edu/Faculty/Matt-Matthews
Department of Mathematics   \ [log in to unmask]
Univ. of Tenn. at Chattanooga\ 423.425.4719       Hint: Use GNU/Linux