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í toán học quốc tế đề tài: Some gregarious cycle decompositions of complete equipartite graphs. | Some gregarious cycle decompositions of complete equipartite graphs Benjamin R. Smith Department of Mathematics University of Queensland Qld 4072 Australia Submitted Aug 17 2009 Accepted Nov 3 2009 Published Nov 13 2009 Mathematics Subject Classification 05C38 05C51 Abstract A k-cycle decomposition of a multipartite graph G is said to be gregarious if each k-cycle in the decomposition intersects k distinct partite sets of G. In this paper we prove necessary and sufficient conditions for the existence of such a decomposition in the case where G is the complete equipartite graph having n parts of size m and either n 0 1 mod k or k is odd and m 0 mod k . As a consequence we prove necessary and sufficient conditions for decomposing complete equipartite graphs into gregarious cycles of prime length. 1 Introduction and preliminaries We begin with some relevant definitions and terminology. Let Kn denote the complete graph on n vertices and Kn denote the empty graph on n vertices. For any graph G and any positive integer A we denote the multigraph obtained from G by replacing each of its edges with A parallel edges by AG. We denote the k-cycle containing edges V1V2 V2V3 . vk-1vk and v1Vk by v1 v2 . Vk or vk Vk-1 . v1 or by any cyclic shift of these. We denote the k-path containing edges V1V2 V2V3 . VkVk 1 by vi V2 . Vk 1 or vk 1 Vk . Vi hence in our terminology a k-path contains k edges and k 1 vertices . Similarly we denote the directed k-cycle containing directed edges v1 v2 v2 v3 . vk-1 vk and vk V1 by v1 v2 . Vk D or by any cyclic shift of this. The lexicographic product 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 g1g2 G E G or g1 g2 and h1h2 G E H . For our purposes we will primarily be concerned with THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R135 1 lexicographic products of the form G Km for some G and m. We note that for all graphs G and positive integers a and Ế G .
