Divisor path decomposition number of a graph

Abstract

A decomposition of a graph G is a collection Ψ of edge-disjoint subgraphs H1,H2,...,HnH1,H2,...,Hn of GG such that every edge of GG belongs to exactly one HiHi. If each HiHi is a path in GG, then ΨΨ is called a path partition or path cover or path decomposition of GG. A divisor path decomposition of a (p,q)(p,q) graph GG is a path cover ΨΨ of GG such that the length of all the paths in ΨΨ divides qq. The minimum cardinality of a divisor path decomposition of GG is called the divisor path decomposition number of GG and is denoted by πD(G)πD(G). In this paper, we initiate a study of the parameter πDπD and determine the value of πDπD for some standard graphs. Further, we obtain some bounds for πDπD and characterize graphs attaining the bounds.