Equipartite Gregarious 5-Cycle Systems and Other Results

A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite 3-cycle systems are 3-GDDs (and so are automatically gregarious), and necessary and sufficient conditions for their existence are known. The cases of equipartite gregarious 4-, 6- and 8-cycle systems have also been dealt with (using techniques that could be applied in the case of any even length cycle). Here we give necessary and sufficient conditions for the existence of a gregarious 5-cycle decomposition of the complete equipartite graph K_m(n) (in effect the first odd length cycle case for which the gregarious constraint has real meaning). In doing so, we also define some general cyclic constructions for the decomposition of certain complete equipartite graphs into gregarious p-cycles (where p is an odd prime).     

Lambda-fold 2-perfect 6-cycle systems in equipartite graphs

A 6-cycle system of a graph G is an edge-disjoint decomposition of G into 6-cycles. Graphs G, for which necessary and sufficient conditions for existence of a 6-cycle system have been found, include complete graphs and complete equipartite graphs. A 6-cycle system of G is said to be 2-perfect if the graph formed by joining all vertices distance 2 apart in the 6-cycles is again an edge-disjoint decomposition of G, this time into 3-cycles, since the distance 2 graph in any 6-cycle is a pair of disjoint 3-cycles.Necessary and sufficient conditions for existence of 2-perfect 6-cycle systems of both complete graphs and complete equipartite graphs are known, and also of λ-fold complete graphs. In this paper, we complete the problem, giving necessary and sufficient conditions for existence of λ-fold 2-perfect 6-cycle systems of complete equipartite graphs.     

Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts

In 1998 Cavenagh [N.J. Cavenagh, Decompositions of complete tripartite graphs into k-cycles, Australas. J. Combin. 18 (1998) 193-200] gave necessary and sufficient conditions for the existence of an edge-disjoint decomposition of a complete equipartite graph with three parts, into cycles of some fixed length k. Here we extend this to paths, and show that such a complete equipartite graph with three partite sets of size m, has an edge-disjoint decomposition into paths of length k if and only if k divides 3m² and k<3m. Further, extending to five partite sets, we show that a complete equipartite graph with five partite sets of size m has an edge-disjoint decomposition into cycles (and also into paths) of length k with k?3 if and only if k divides 10m² and k?5m for cycles (or k<5m for paths).     

Path and cycle decompositions of complete equipartite graphs: Four parts

We show that a complete equipartite graph with four partite sets has an edge-disjoint decomposition into cycles of length k if and only if k≥3, the partite set size is even, k divides the number of edges in the equipartite graph and the total number of vertices in the graph is at least k. We also show that a complete equipartite graph with four even partite sets has an edge-disjoint decomposition into paths with k edges if and only if k divides the number of edges in the equipartite graph and the total number of vertices in the graph is at least k+1.     

Decomposing complete equipartite graphs into odd square‐length cycles: number of parts odd

In this article, we introduce a new technique for obtaining cycle decompositions of complete equipartite graphs from cycle decompositions of related multigraphs. We use this technique to prove that if n, m and λ are positive integers with n ≥ 3, λ≥ 3 and n and λ both odd, then the complete equipartite graph having n parts of size m admits a decomposition into cycles of length λ² whenever nm ≥ λ² and λ divides m. As a corollary, we obtain necessary and sufficient conditions for the decomposition of any complete equipartite graph into cycles of length p², where p is prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:401‐414, 2010     

On the Existence of Elementary Abelian Cycle Systems

We present some necessary and/or sufficient conditions for the existence of an elementary abelian cycle system of the complete graph. We propose a construction for some classes of perfect elementary abelian cycle systems. Finally we consider elementary abelian k-cycle systems of the complete multipartite graph.      

Closed trail decompositions of complete equipartite graphs

The complete equipartite graph $K_m * {\overline{K_n}}$ has mn vertices partitioned into m parts of size n, with two vertices adjacent if and only if they are in different parts. In this paper, we determine necessary and sufficient conditions for the existence of a decomposition of $K_m * {\overline{K_n}}$ into closed trails of length k. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 374–403, 2009     

Resolvable gregarious cycle decompositions of complete equipartite graphs

The complete multipartite graph K_n(m) with n parts of size m is shown to have a decomposition into n-cycles in such a way that each cycle meets each part of K_n(m); that is, each cycle is said to be gregarious. Furthermore, gregarious decompositions are given which are also resolvable.     

Decomposing complete equipartite graphs into short even cycles

In this article we find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both even and short relative to the number of parts. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:131‐143, 2011     

Planar graphs without specific cycles are 2-degenerate

A graph G is k-degenerate if each subgraph of G has a vertex of degree at most k. It is known that every simple planar graph with girth 6, or equivalently without 3-, 4-, and 5-cycles, is 2-degenerate. In this work, we investigate for which k every planar graph without 4-, 6-, … , and 2k-cycles is 2-degenerate. We determine that k is 5 and the result is tight since the truncated dodecahedral graph is a 3-regular planar graph without 4-, 6-, and 8-cycles. As a related result, we also show that every planar graph without 4-, 6-, 9-, and 10-cycles is 2-degenerate.