Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài:Decomposing complete equipartite graphs into short odd cycles. | Decomposing complete equipartite graphs into short odd cycles Benjamin R. Smith Centre for Discrete Mathematics and Computing Department of Mathematics The University of Queensland Qld 4072 Australia bsmith@ Nicholas J. Cavenagh The Department of Mathematics The University of Waikato Private Bag 3105 Hamilton New Zealand School of Mathematical Sciences Monash University Vic 3800 Australia nickc@ Submitted Jun 3 2009 Accepted Sep 6 2010 Published Sep 22 2010 Mathematics Subject Classification 05C38 05C51 Abstract In this paper we examine the problem of decomposing the lexicographic product of a cycle with an empty graph into cycles of uniform length. We determine necessary and sufficient conditions for a solution to this problem when the cycles are of odd length. We apply this result to find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length in the case that the length is both odd and short relative to the number of parts. 1 Introduction Before we venture further we remind the reader of some definitions. A complete equipartite graph Kn m has its nm vertices partitioned into n parts often referred to as partite sets each of size m and there is an edge between any two vertices in different partite sets but no edge between any two vertices in the same partite set. The lexicographic product THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R130 1 G H of graphs G and H is the graph with vertex set V G X V H and with an edge joining g1 h1 to g2 h2 if and only if g1 is adjacent to g2 in G or g1 g2 and h1 is adjacent to h2 in H. Observe that Kn m is isomorphic to Kn Km. We frequently exploit the following elementary facts abouts the lexicographic product. For any graph G G Km K G Km . Also if G has an edge-disjoint decomposition into subgraphs G1 G2 . Gt then G Km has an edge-disjoint decomposition into subgraphs G1 Km G2 Km . Gt Km. With the above observations it should come as no .
