Decomposition of Graphs into Induced Paths and Cycles

A decomposition of a graph G is a collection ψ of subgraphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path or an induced cycle in G, then ψ is called an induced path decomposition of G. The minimum cardinality of an induced path decomposition of G is called the induced path decomposition number of G and is denoted by πi(G). In this paper we initiate a study of this parameter.

Induced Acyclic Path Decomposition in Graphs

A decomposition of a graph G is a collection ψ of graphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path in G, then ψ is called an induced acyclic path decomposition of G and if each Hi is a (induced) cycle in G then ψ is called a (induced) cycle decomposition of G. The minimum cardinality of an induced acyclic path decomposition of G is called the induced acyclic path decomposition number of G and is denoted by ¤Çia(G). Similarly the cyclic decomposition number ¤Çc(G) is defined. In this paper we begin an investigation of these parameters.