A STUDY ON INDUCED PATH DECOMPOSITIONS OF GRAPHS

Abstract

A graph is a discrete structure consisting of a set of objects called vertices and another set of objects called edges depicting the relationship between pairs of vertices. Therefore, graphs serve as effective models to study networks of all types such as computer networks, telecommunication networks and social networks. The concept of a graph possesses the unique combination of features like simplicity, visibility, beauty, clarity, elegance and effectiveness in studying problems dealing with network structures. It might be a simple structure like that of an organizational structure in a college, a complex structure like the world wide web (www)or just an abstract structure consisting of objects that are interconnected according to some rule. In specific terms, by a graph G = (V, E) we mean a nontrivial, connected and finite undirected graph without loops (an edge containing just one vertex) and multiple edges (more than one edge joining the same pair of vertices). The order and size of G are the cardinality |V | of V and |E| of E, denoted by n and m respectively. For graph theoretic terminology and notation, not specifically mentioned in this thesis, the reader may refer to Chartrand and Lesniak [19], Harary [25] and Bondy and Murty [18]. viiiThe growth of graph theory from the status of being one of the topics in combinatorics to an important branch of mathematics within a short period of time is an indicator of the relevance, significance and interest of mathematicians for research in graph theory. Some of the areas in graph theory where a significant amount of studies have been carried out by researchers in India are decomposition problems, theory of domination, coloring and labeling. The problems explored are varying in nature. They include existence problems that deal with the problem of proving or disproving the existence of a particular structure, enumeration problems that are concerned with the number of graphs with a specified property, evaluation problems involving the determination of the related parameter for a given graph, extremal problems and optimization problems. A decomposition of a graph G is a collection ψ of subgraphs of G whose edge sets form a partition of the edge set of G. The subgraphs of the decomposition ψ are called parts of the decomposition. If each part of ψ is a path or a cycle, then ψ is called a path decomposition. This topic is as old as Leonhard E¨uler, the originator of modern graph theory, who gave a characterizationof a graph decomposable into cycles, the so-called Eulerian graph. ixThe initial phase of research in graph decompositions during the nineteenth century primarily dealt with combinatorial problems falling under the purview of recreational mathematics. The uproar caused by the attempts to solve the celebrated four color problem brought in a revived interest in graph theory research and the development of computational technology accelerated its growth further. Juraj Bos´ak’s monograph on graph decompositions [29] is a good resource book that gives a comprehensive picture of the studies in graph decompositions till the year 1985. In this thesis, some problems pertaining to path decomposition of graphs are presented. The main focus of the study is on decomposition of graphs into induced paths and cycles. The concept of path decomposition was first introduced by Harary [26] in the year 1970 and was studied further by Harary and Schwenk [27], Stanton, Cowan and James [47] and later by Peroche [34]. Following Harary, several variations of path decompositions were introduced by researchers by imposing various conditions on the paths. Among the recent studies on path decomposition, we have induced path decomposition introduced by Sahul Hamid and Abraham [38], equiparity path decomposition due to K. Nagarajan, A. Nagarajan and Sahul Hamid [31] and (a, b) decomposition introduced by Teypaz and Rapine [50]. xAcharya and Sampathkumar [6] introduced yet another variation of path decomposition in the name of graphoidal decomposition (originally called graphoidal cover) of graphs to be a path decomposition in which no vertex of the graph is internal to more than one member in the path decomposition...