Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Decompositions of graphs into 5-cycles and other small graphs. | Decompositions of graphs into 5-cycles and other small graphs Teresa Sousa Tepper School of Business Carnegie Mellon University Pittsburgh PA 15213 tmj@ Submitted Jan 13 2005 Accepted Aug 31 2005 Published Sep 29 2005 Mathematics Subject Classifications 05C35 05C70 Abstract In this paper we consider the problem of finding the smallest number q such that any graph G of order n admits a decomposition into edge disjoint copies of a fixed graph H and single edges with at most q elements. We solve the case when H is the 5-cycle the 5-cycle with a chord and any connected non-bipartite non-complete graph of order 4. 1 Introduction Let G be a simple graph with vertex set V and edge set E. The number of vertices of a graph is its order. The degree of a vertex v is the number of edges that contain v and will be denoted by degG v or simply by deg v. For A c V deg v A denotes the number of neighbors of v in the set A. The set of neighbors of v is denoted by NG v or briefly by N v if it is clear which graph is being considered. Let NG v V NG v u v . The complete bipartite graph with parts of size m and n will be denoted by Km n and the cycle on n vertices will be denoted by Cn. The chromatic number of G is denoted by x G . Let JC be a family of graphs. An JC-decomposition of G is a set of subgraphs G1 . Gt such that any edge of G is an edge of exactly one of G1 . Gt and all G1 . Gt 2 AE. Let b G C denote the minimum size of an JC-decomposition of G. The main problem related to JC-decompositions is the one of finding the smallest number ộ n AE such that every graph G of order n admits an JC-decomposition with Research supported in part by the Portuguese Science Foundation under grant SFRH BD 8617 2002 THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R49 1 at most ộ n JÍ elements. Here we address this problem for the special case where consists of a fixed graph H and the single edge graph. Let H be a graph with m edges and let ex n H denote the maximum number of .
