tailieunhanh - Báo cáo toán học: "H-Decompositions of r-graphs when H is an r-graph with exactly 2 edges"

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: H-Decompositions of r-graphs when H is an r-graph with exactly 2 edges. | H-Decompositions of r-graphs when H is an r-graph with exactly 2 edges Teresa Sousa Departamento de Matematica FCT-UNL and CMA-UNL Quinta da Torre 2829-516 Caparica Portugal tmj s@ Submitted Dec 15 2008 Accepted Mar 1 2010 Published Mar 8 2010 Mathematics Subject Classification 05C88 Abstract Given two r-graphs G and H an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. The minimum number of parts in an H -decomposition of G is denoted by ộrH G . By a 2-edge-decomposition of an r-graph we mean an H-decomposition for any fixed r-graph H with exactly 2 edges. In the special case where the two edges of H intersect in exactly 1 2 or r 1 vertices these 2-edge-decompositions will be called bowtie domino and kite respectively. The value of the function ộrH n will be obtained for bowtie domino and kite decompositons of r-graphs. 1 Introduction An hypergraph is a finite set V V G called the vertices of G together with a set E E G of non-empty subsets of any cardinality of V called the hyperedges or edges. When all the edges of an hypergraph are distinct we say that the hypergraph is simple. If in addition all the edges have the same cardinality r 2 then G is said to be a uniform hypergraph or an r-graph. Thus graphs are special hypergraphs. The number of vertices of an hypergraph is its order and is denoted by v G . The number of edges in an hypergraph is its size and is denoted by e G . The complete r-graph on n vertices is the hypergraph that consists of all r-subsets of V and it will be denoted by Kf. We denote by n the set of the first n integers. Given two r-graphs G and H with r 2 an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. The minimum number of parts in an H-decomposition of G is denoted by w n G . This work was partially supported by Financiamento Base 2009 ISFL-1-297 from FCT .