Journal of Prime Research in Mathematics

Divisor path decomposition number of a graph

K. Nagarajan
Department of Mathematics, Sri S.R.N.M.College, Sattur – 626 203, Tamil Nadu, India.
A. Nagarajan
Department of Mathematics, V.O.C.College, Tuticorin – 628 008, Tamil Nadu, India.

\(^{1}\)Corresponding Author:


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


Divisor path, greatest divisor path, divisor path decomposition, divisor path decomposition number.