Induced Graphoidal Decompositions in Product Graphs

Let be a nontrivial, simple, finite, connected, and undirected graph. A graphoidal decomposition (GD) of is a collection of nontrivial paths and cycles in that are internally disjoint such that every edge of lies in exactly one member of . By restricting the members of a GD to be induced, the concept of induced graphoidal decomposition (IGD) of a graph has been defined. The minimum cardinality of an IGD of a graph is called the induced graphoidal decomposition number and is denoted by ( ). An IGD of without any cycles is called an induced acyclic graphoidal decomposition (IAGD) of , and the minimum cardinality of an IAGD of is called the induced acyclic graphoidal decomposition number of , denoted by ( ). In this paper we determine the value of ( ) and ( ) when is a product graph, the factors being paths/cycles. 1. Introduction By a graph we mean a nontrivial, finite, connected, and undirected graph having no loops and multiple edges. The order and size of graph are denoted by and respectively. For terms not defined here we refer the reader to [1]. A decomposition of is a collection of edge-disjoint subgraphs of such that every edge of belongs to exactly one . Graph decomposition problems constitute a major area of research because of their theoretical and practical implications. Designing interconnection networks and drug designing are examples for the application of graph decomposition problems. Among the variants of decompositions of graphs that abound in the literature, path decomposition problems assume a prominent position. Harary [2] introduced the concept of path decomposition of graphs in 1970 which was further studied by Harary and Schwenk [3], Péroche [4], and Stanton et al. [5]. As a special case of path decomposition, Acharya and Sampathkumar [6] introduced the notion of graphoidal decomposition which is a decomposition of a graph into internally disjoint paths/cycles. By imposing the condition that the members of a graphoidal decomposition are induced paths/cycles, Arumugam [7] introduced the concept of induced graphoidal decomposition as well as that of induced acyclic graphoidal decomposition. Studies on these decompositions were initiated by Ratan Singh and Das [8, 9] and were further extended by Sahul Hamid and Joseph [10, 11] by obtaining certain bounds of the related parameters and and solving some characterization problems. In this paper we determine the value of and for a class of product graphs, namely, products of paths and cycles. 2. Induced Graphoidal Decomposition The concept of graphoidal cover (we say graphoidal