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