Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Sharply transitive 1-factorizations of complete multipartite graphs"

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 mazzuoccolo.giuseppe@unimore.it .