Đ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 trên tạp chí toán học quốc tế đề tài: One-Factorizations of Regular Graphs of Order 12. | One-Factorizations of Regular Graphs of Order 12 Petteri Kaski Department of Computer Science and Engineering Helsinki University of Technology P.O. Box 5400 FI-02015 TKK Finland petteri.kaski@hut.fi Patric R. J. Ostergảrd Department of Electrical and Communications Engineering Helsinki University of Technology P.O. Box 3000 FI-02015 TKK Finland patric.ostergard@hut.fi Submitted Oct 5 2004 Accepted Dec 6 2004 Published Jan 7 2005 Mathematics Subject Classifications 05C70 05-04 Abstract Algorithms for classifying one-factorizations of regular graphs are studied. The smallest open case is currently graphs of order 12 one-factorizations of r-regular graphs of order 12 are here classified for r 6 and r 10 11. Two different approaches are used for regular graphs of small degree these proceed one-factor by one-factor and vertex by vertex respectively. For degree r 11 we have one-factorizations of K12. These have earlier been classified but a new approach is presented which views these as certain triple systems on 4n 1 points and utilizes an approach developed for classifying Steiner triple systems. Some properties of the classified one-factorizations are also tabulated. 1 Introduction An r-factor of a graph G is an r-regular spanning subgraph of G. An r-factorization of G is a partition of the edges of G into r-factors. We consider here one-factorizations alternatively 1-factorizations of small regular graphs of even order 2n and degree 1 k 2n 1. The complete graph K2n is the unique regular graph of order 2n and degree 2n 1. Research supported by the Helsinki Graduate School in Computer Science and Engineering HeCSE and a grant from the Foundation of Technology Helsinki Finland Tekniikan Edistamissaatio . Research supported by the Academy of Finland under Grants No. 100500 and 202315. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R2 1 Two one-factorizations are isomorphic if there exists a bijection between the vertices of the graphs that maps one-factors onto .
