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: k_nagarajan_srnmc@yahoo.co.in

### Abstract

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.

#### Keywords:

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