Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: k-cycle free one-factorizations of complete graphs. | k-cycle free one-factorizations of complete graphs Mariusz Meszka Faculty of Applied Mathematics AGH University of Science and Technology Al. Mickiewicza 30 30-059 Krakow Poland meszkaagh.edu.pl Submitted Dec 5 2007 Accepted Dec 10 2008 Published Jan 7 2009 Mathematics Subject Classifications 05C70 Abstract It is proved that for every n 3 and every even k 4 where k 2n there exists one-factorization of the complete graph K2n such that any two one-factors do not induce a graph with a cycle of length k as a component. Moreover some infinite classes of one-factorizations in which lengths of cycles induced by any two one-factors satisfy a given lower bound are constructed. 1 Introduction A one-factor of a graph G is a regular spanning subgraph of degree one. A one-factorization of G is a set F F1 F2 . Fng of edge-disjoint one-factors such that E G un 1 E Fj . Evidently the union of two edge-disjoint one-factors is a two-factor consisting of cycles of even lengths. The exact number N 2n of all pairwise non-isomorphic one-factorizations of the complete graph K2n is known only for 2n 14 namely N 4 N 6 1 N 8 6 N 10 396 cf. 14 N 12 526 915 620 8 and N 14 1 132 835 421 602 062 347 10 . Moreover Cameron 4 proved that ln N 2n 2n2 ln 2n for sufficiently large n. Therefore any investigations including enumeration regarding all one-factorizations of K2n are deemed reasonable if they are restricted to a subclass which satisfies some additional properties. One of the obvious requirements concerns an isomorphism of graphs induced by pairs of one-factors. In this way a question arises regarding the existence of uniform perfect one-factorizations. A one-factorization is uniform when the union of any two one-factors is isomorphic to the same graph H. In particular if H is connected i.e. a Hamiltonian cycle then a one-factorization is called perfect. Perfect one-factorizations of complete graphs were introduced by Kotzig 11 and in known notation by Anderson 2 . Only three infinite .