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).     

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.     

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).     

Symmetric Hamilton cycle decompositions of the complete graph

We construct a new symmetric Hamilton cycle decomposition of the complete graph K_n for odd n > 7. © 2003 Wiley Periodicals, Inc.     

完全图与完全n部图的完全多部图分解

§ 1　IntroductionLet V(G) and E(G) be the vertex setand the edge setof a graph G,respectively.Fori=1 ,...,p,if V(Gi) V(G) ,E(Gi)∩ E(Gj) = for i≠ j,and∪pi=1 E(Gi) =E(G) ,then wecall{ G1 ,...,GP} a decomposition of G.Let[i,j] be the integer interval including i and j.Let Knbe a complete graph with the vertex set[1 ,n] .For m disjointsubsets A1 ,...Amof[1 ,n] ,let K(A1 ,...,Am) be a complete m-partite graph having partite-sets A1 ,...,Am.If| Ai| =1 ,Ai is called a S-set;otherwi…     

A Construction of a perfect set of Euler tours of K2k+1

In this article we prove Kotzig's Conjecture by constructing a perfect set of Euler tours of K_2k+1. As a corollary, we deduce that L(K_2k+1), the line graph of K_2k+1, has a Hamilton decomposition. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 215–230, 1997     

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.     

完全图中的正常染色的路和圈

令$K_{n}^{c}$表示$n$ 个顶点的边染色完全图.
令 $Delta^{mon}
(K_{n}^{c})$表示$K^c_{n}$的顶点上关联的同种颜色的边的最大数目.
如果$K_{n}^{c}$中的一个圈（路）上相邻的边染不同颜色,则称它为正常染色的.
B. Bollob'{a}s和P. Erd\"{o}s (1976) 提出了如下猜想：若 $Delta^{{mon}}
(K_{n}^{c})色的Hamilton圈. 这个猜想至今还未被证明.我们研究了上述条件下的正常染色的路和圈.