Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Permutation Separations and Complete Bipartite Factorisations of Kn,n. | Permutation Separations and Complete Bipartite Factorisations of Kn n Nigel Martin Department of Mathematics University of Durham Durham . Richard Stong Department of Mathematics Rice Univeristy Houston TX USA stong@ Submitted Apr 14 2003 Accepted Aug 29 2003 Published Sep 17 2003 MR Subject Classifications 05C70 Abstract Suppose p q are odd and relatively prime. In this paper we complete the proof that Kn n has a factorisation into factors F whose components are copies of Kp q if and only if n is a multiple of pq p q . The final step is to solve the c-value problem of Martin. This is accomplished by proving the following fact and some variants For any 0 k n there exists a sequence n1 n2 . n2fc i of not necessarily distinct permutations of 1 2 . n such that each value in k 1 k . k occurs exactly n times as nj i i for 1 j 2k 1 and 1 i n. 1 Introduction This goal of this paper is to complete the study of factorisation of balanced complete bipartite graphs Kn n into factors each of whose components are Kp q. This subject began with the study of star-factorisations where all components are K1k for some fixed k of complete bipartite graphs by Ushio 5 Ushio and Tsuruno 6 Wang 7 and Du 1 . The results were extended to factorisations where the components are Kp q by Martin in a sequence of papers 2 3 and 4 . Specifically we make the following definition. Definition . Let F and G be simple undirected graphs. An F-factor of G is a spanning subgraph of G whose components are all isomorphic to F. A complete F-factorisation of G is a decomposition of G as a union of edge-disjoint F -factors. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R37 1 The first paper in the sequence 2 derives necessary conditions for a Kp q-factorisation of Km n called the Basic Arithmetic Conditions BAC . The natural BAC Conjecture states that these BAC conditions are also sufficient for a Kp q-factorisation. In addition 2 shows that it suffices to consider .
