Some equitably 3-colourable cycle decompositions of complete equipartite graphs

Let G be a graph in which each vertex has been coloured using one of k colours, say c(1), c(2),.. , c(k). If an m-cycle C in G has n(i) vertices coloured c(i), i = 1, 2,..., k, and vertical bar n(i) - n(j)vertical bar <= 1 for any i, j is an element of {1, 2,..., k}, then C is said to be equitably k-coloured. An m-cycle decomposition C of a graph G is equitably k-colourable if the vertices of G can be coloured so that every m-cycle in W is equitably k-coloured. For m = 3, 4 and 5 we completely settle the existence question for equitably 3-colourable m-cycle decompositions of complete equipartite graphs. (c) 2005 Elsevier B.V. All rights reserved.

Packing lambda-fold complete multipartite graphs with 4-cycles

A maximum packing of any lambda-fold complete multipartite graph (where there are lambda edges between any two vertices in different parts) with edge-disjoint 4- cycles is obtained and the size of each minimum leave is given. Moreover, when lambda =2, maximum 4-cycle packings are found for all possible leaves.

Decomposition of complete graphs into 5-cubes

Necessary conditions for the complete graph on n vertices to have a decomposition into 5-cubes are that 5 divides it - 1 and 80 divides it (it - 1)/2. These are known to be sufficient when n is odd. We prove them also sufficient for it even, thus completing the spectrum problem for the 5-cube and lending further weight to a long-standing conjecture of Kotzig. (c) 2005 Wiley Periodicals, Inc.

Some equitably 2-colourable cycle decompositions of multipartite graphs

Let G be a graph in which each vertex has been coloured using one of k colours, say c(1), c(2),..., c(k). If an m-cycle C in G has x(i) vertices coloured c(i), i = 1, 2,..., k, and vertical bar x(i) - x(j)vertical bar

On Hamilton cycle decomposition of 6-regular circulant graphs

The circulant graph Sn, where S ⊆ Zn \ {0}, has vertex set Zn and edge set {{x, x + s}|x ∈ Zn, s ∈ S}. It is shown that there is a Hamilton cycle decomposition of every 6-regular circulant graph Sn in which S has an element of order n.