|
Organizers |
3-path decompostition of complete graphs with no subsystems
by
Chandra Dinavahi
Auburn University
Coauthors: C. A. Rodger
A 3-path decomposition of a complete graph is an ordered pair (V, P) where V is the vertex set of the complete graph, and P is a set of paths of length 3, the edges of which partition the edge set of the complete graph. (V, P) is said to have no subsystems if there exists no ordered pair (W, Q) that is a 3-path decompostion, where W is a subset of V and Q is a subset of P. In this talk, it is shown that such decompositions exist if and only if the number of vertices is 0 or 1 (mod 3). Packing versions of this problem have also been solved, as have decompositions for graphs other than 3-paths.
Date received: October 14, 2005
Copyright © 2005 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # carm-82.