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: Sharply transitive 1-factorizations of complete multipartite graphs. | Sharply transitive 1-factorizations of complete multipartite graphs Giuseppe Mazzuoccolo and Gloria Rinaldi t Submitted Apr 23 2009 Accepted May 17 2010 Published May 25 2010 Mathematics Subject Classification 05C25 05C70 Abstract Given a finite group G of even order which graphs r have a 1 factorization admitting G as automorphism group with a sharply transitive action on the vertex-set Starting from this question we prove some general results and develop an exhaustive analysis when r is a complete multipartite graph and G is cyclic. 1 Introduction A 1 factor of a graph is a collection of edges such that each vertex is incident with exactly one edge. A 1 factorization of a regular graph is a partition of the edge-set of the graph into disjoint 1 factors. If the graph has valency v then a 1 factorization is equivalent to a coloring of the edges in v colors one color for each 1 factor . The problem of establishing whether a finite simple regular graph r is 1 factorizable or not may be an hard task. In fact the 1 factorization problem is NP-complete in general. An obviously necessary condition for the existence of a 1 factorization is that the number of vertices must be even. So far the best known sufficient condition is that regular graphs of order 2n and valency v a 7 1 n are 1 factorizable 6 . For graphs r with 1 factorization then an automorphism group G of the 1 factorization is a permutation group of the vertex-set of r which maps 1 factors onto 1 factors. The action of G is said to be sharply transitive on the vertex-set if for any given pair of not necessarily distinct vertices x y there exists a unique automorphism g in G mapping x to y. Obviously the order of G is equal to the number of vertices in this case. It is well-known that complete graphs are 1 factorizable and in many recent papers the following question was addressed. Dipartimento di Matematica Universita di Modena e Reggio Emilia via Campi 213 B Italy. email .
