Induced graphoidal decompositions in product graphs (Q2249943)

Summary: Let \(G\) be a nontrivial, simple, finite, connected, and undirected graph. A graphoidal decomposition (GD) of \(G\) is a collection \(\psi\) of nontrivial paths and cycles in \(G\) that are internally disjoint such that every edge of \(G\) lies in exactly one member of \(\psi\). By restricting the members of a GD \(\psi\) 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 \(G\) is called the induced graphoidal decomposition number and is denoted by \(\eta_i(G)\). An IGD of \(G\) without any cycles is called an induced acyclic graphoidal decomposition (IAGD) of \(G\), and the minimum cardinality of an IAGD of \(G\) is called the induced acyclic graphoidal decomposition number of \(G\), denoted by \(\eta_{ia}(G)\). In this paper we determine the value of \(\eta_i(G)\) and \(\eta_{ia}(G)\) when \(G\) is a product graph, the factors being paths/cycles.