Đ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 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: Graph products and new solutions to Oberwolfach problems. | Graph products and new solutions to Oberwolfach problems Gloria Rinaldi Dipartimento di Scienze e Metodi dell Ingegneria Università di Modena e Reggio Emilia 42100 Reggio Emilia Italy gloria.rinaldi@unimore.it Tommaso Traetta Dipartimento di Matematica Università Sapienza di Roma 00185 Roma Italy traetta@mat.uniromal.it Submitted Sep 21 2010 Accepted Feb 17 2011 Published Mar 11 2011 Mathematics Subject Classifications 05C51 05C70 05C76 Abstract We introduce the circle product a method to construct simple graphs starting from known ones. The circle product can be applied in many different situations and when applied to regular graphs and to their decompositions a new regular graph is obtained together with a new decomposition. In this paper we show how it can be used to construct infinitely many new solutions to the Oberwolfach problem in both the classic and the equipartite case. 1 Introduction In this paper we will only deal with undirected simple graphs. For each graph r we will denote by V r and E r its vertex-set and edge-set respectively. By Kv we will denote the complete graph on v vertices and by K s r the complete equipartite graph having r parts of size s. The number of edges incident with a vertex a is called the degree of a in r and is denoted dr a . We will drop the index referring to the underlying graph if the reference is clear. All over the paper we will consider graphs without isolated vertices i.e. vertices of degree zero. It is well known that a graph in which all vertices have the same degree t is called t-regular or simply regular. By Cn a1 . an we will denote a cycle of length n namely a simple graph with vertices a1 . an and edges ai ai 1 where the indices are to be considered modulo n. Also by r1 ur2 we will denote the disjoint union of two graphs namely V r1 n V r2 0 V ri u r2 V ri u V r2 and E Ế1 LI 2 E ri u E r2 . A decomposition of a graph K is a set F r1 . rt of subgraphs of K whose edges partition altogether the edge-set of K. If all
