Decomposing graphs into internally-disjoint induced paths

Abstract

Let \(G\) be a non-trivial, simple, finite, connected and undirected graph. An acyclic graphoidal decomposition \( (AGD)\) of  \(G\) is a collection \(\psi\) of non-trivial paths in  \(G\) that are internally vertex-disjoint such that every edge of \(G\)  lies in exactly one path of \(\psi\). By imposing the condition of induceness on the paths in \(\psi\), the concept of induced acyclic graphoidal decomposition \( (IAGD)\) of a graph  \(G\) has been defined in [2]. The minimum number of paths in such a decomposition of  \(G\) is called the induced acyclic graphoidal decomposition number denoted by \( \eta_{ia}(G)\). In this paper we obtain certain bounds of the parameter \(\eta_{ia}(G)\) and initiate a study on graphs admitting an \(IAGD\) satisfying the Helly property.