Induced Graphoidal Decompositions in Product Graphs

Abstract EN

Let G be a nontrivial, simple, finite, connected, and undirected graph.

A graphoidal decomposition (GD) of G is a collection ψ of nontrivial paths and cycles in G that are internally disjoint such that every edge of G 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 G is called the induced graphoidal decomposition number and is denoted by η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 ηia(G).

In this paper we determine the value of ηi(G) and ηia(G) when G is a product graph, the factors being paths/cycles.