Common multiples of complete graphs and a 4-cycle

A graph G is a common multiple of two graphs H-1 and H-2 if there exists a decomposition of G into edge-disjoint copies of H-1 and also a decomposition of G into edge-disjoint copies of H-2. In this paper, we consider the case where H-1 is the 4-cycle C-4 and H-2 is the complete graph with n vertices K-n. We determine, for all positive integers n, the set of integers q for which there exists a common multiple of C-4 and K-n having precisely q edges. (C) 2003 Elsevier B.V. All rights reserved.

Decompositions of complete graphs into triangles and Hamilton cycles

For all odd integers n greater than or equal to 1, let G(n) denote the complete graph of order n, and for all even integers n greater than or equal to 2 let G,, denote the complete graph of order n with the edges of a 1-factor removed. It is shown that for all non-negative integers h and t and all positive integers n, G, can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in G(n). (C) 2004 Wiley Periodicals, Inc.

Edge-coloured cube decompositions

An edge-colored graph is a graph H together with a function f:E(H) → C where C is a set of colors. Given an edge-colored graph H, the graph induced by the edges of color c C is denoted by H(c). Let G, H, and J be graphs and let μ be a positive integer. A (J, H, G, μ) edge-colored graph decomposition is a set S = {H 1,H 2,...,H t} of edge-colored graphs with color set C = {c 1, c 2,..., c k} such that Hi ≅ H for 1 ≤ i ≤ t; Hi (cj) ≅ G for 1 ≤ i ≤ t and ≤ j ≤ k; and for j = 1, 2,..., k, each edge of J occurs in exactly μ of the graphs H 1(c j ), H 2(c j ),..., H t (c j ). Let Q 3 denote the 3-dimensional cube. In this paper, we find necessary and sufficient conditions on n, μ and G for the existence of a (K n ,Q 3,G, μ) edge-colored graph decomposition. © Birkhäuser Verlag, Basel 2007.

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.

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.