05912066

j

05912066 Nagarajan, K. Nagarajan, A. Co prime path decomposition number of a graph. An. \c Stiin\c t. Univ. ``Ovidius" Constan\c ta, Ser. Mat. 19, No. 1, 223-236 (2011). 2011 Universitatea ``Ovidius", Constan\c ta EN co prime path co prime path decomposition co prime path decomposition Summary: A ``decomposition" of a graph $G$ is a collection $\psi$ of edge-disjoint subgraphs $H_1,H_2,\dots,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 $\psi$ is called a ``path partition" or ``path cover" or ``path decomposition" of $G$. A ``co-prime path decomposition" of a $(p,q)$-graph $G$ is a path cover $\psi$ of $G$ such that the length of all the paths in $\psi$ are co-prime with $q$. The minimum cardinality of a co-prime path decomposition of $G$ is called the ``co-prime path decomposition number" of $G$ and is denoted by $\pi_\phi(G)$. In this paper, a study of the parameter $\pi_\phi$ is initiated and the value of $\pi_\phi$ for some standard graphs is determined. Further, bounds for $\pi_\phi$ are obtained and the graphs attaining the bounds are characterized.