DEPARTMENT OF MATHEMATICS
       ALGEBRA AND COMBINATORICS SEMINAR

  1PM THURSDAY 29 APRIL 2004  in 43-102


     On the cyclic decomposition of complete
       graphs into almost-bipartite graphs

               Andrew Blinco
          Department of Mathematics,
           University of Queensland


Abstract
Techniques of labelling the vertices of a bipartite graph G 
with n edges to yield cyclic G-decompositions of the complete 
graphs K_{2nx+1} have received much attention in the literature. 
An almost-bipartite graph is a non-bipartite graph with the 
property that the removal of a (possibly particular) single edge 
renders the graph bipartite. Examples of such graphs
include the odd cycles. Here we introduce the concept of a
\gamma-labelling of an almost-bipartite graph and show that 
if an almost-bipartite graph G with n edges has a \gamma-labelling 
then there is a cyclic G-decomposition of K_{2nx+1} for all 
positive integers x.

All welcome.


-------------------
Pete Jenkins
pdj@maths.uq.edu.au