Decomposition of Graphs into Paths and Cycles

A decomposition of a graph is a collection of edge-disjoint subgraphs of such that every edge of belongs to exactly one . If each is a path or a cycle in , then is called a path decomposition of . If each is a path in , then is called an acyclic path decomposition of . The minimum cardinality of a path decomposition (acyclic path decomposition) of is called the path decomposition number (acyclic path decomposition number) of and is denoted by ( ) ( ( )). In this paper we initiate a study of the parameter and determine the value of for some standard graphs. Further, we obtain some bounds for and characterize graphs attaining the bounds. We also prove that the difference between the parameters and can be made arbitrarily large. 1. Introduction Graph decomposition problems rank among the most prominent areas of research in graph theory and combinatorics and further it has numerous applications in various fields such as networking, block designs, and bioinformatics. A decomposition of a graph is a collection of edge-disjoint subgraphs of such that every edge of belongs to exactly one . Various types of path decompositions and corresponding parameters have been studied by several authors by imposing conditions on the paths in the decomposition. It is obvious that every graph admits a decomposition in which each subgraph is either a path or a cycle. In this connection, Erd s asked what is the minimum number of paths into which every connected graph on vertices can be decomposed and Gallai conjectured that this number is at most as stated below. Gallai's Conjecture (see？？[1]). ？If is a connected graph on vertices, then can be decomposed into paths. A good number of research articles have been published in which Gallai's is the focus of study and still this conjecture remains unsettled for more than 30 years. Towards a proof of the conjecture, Lovasz [1] made the first significant contribution by proving the following theorem. Theorem 1 (see [1]). A graph on vertices (not necessarily connected) can be decomposed into paths and cycles. Gallai's conjecture and Theorem 1 motivate the following definition. Definition 2. Let be a decomposition of a graph . If each is either a path or a cycle, then is called a path decomposition of . If each is a path, then is called an acyclic path decomposition of . The minimum cardinality of a path decomposition of is called the path decomposition number. Similarly the acyclic path decomposition number of is defined and is denoted by . The parameter was introduced by Harary and further studied extensively by Harary and Schwenk