A decomposition of a graph $G$ is a collection of its edge disjoint sub-graphs such that their union is $G$. A path decomposition of a graph is a decomposition of it into paths. In this paper, we define the pendant number $\Pi_p$ as the minimum number of end vertices of paths in a path decomposition of $G$ and determine this parameter for certain fundamental graph classes.

Citation details of the article

Journal: International Journal of Applied Mathematics
Journal ISSN (Print): ISSN 1311-1728
Journal ISSN (Electronic): ISSN 1314-8060
Volume: 31
Issue: 5
Year: 2018

DOI: 10.12732/ijam.v31i5.12

Download Section

Download the full text of article from here.

You will need Adobe Acrobat reader. For more information and free download of the reader, please follow this link.


  1. [1] B. Alspach, J.C. Bermond, D. Sotteau, Decomposition into cycles I: Hamilton decompositions, In: Cycles and Rays, Springer (1990), 9-18.
  2. [2] S. Arumugam, I. Hamid, V.M. Abraham, Decomposition of graphs into paths and cycles, J. Discrete Math., 2013 (2013), 1-6, DOI: 10.1155/2013/721051.
  3. [3] S. Arumugam, J.S. Suseela, Acyclic graphoidal covers and path partitions in a graph, Discrete Math., 190, No 1-3 (1998), 67-77, DOI: 10.1016/S0012-365X(98)00032-6.
  4. [4] F. Harary, Graph Theory, Narosa Publ. House, New Delhi (2001).
  5. [5] K. Heinrich, Path decompositions, Le Matematiche, XLVII (1992), 241-258.
  6. [6] R.G. Stanton, D.D. Cowan, L.O. James, Some results on path numbers, In: Graph Theory and Computing, Proc. Louisiana Conf. on Combin. (1970), 112-135.
  7. [7] D.B. West, Introduction to Graph Theory, Prentice Hall of India, New Delhi (2005).
  8. [8] Information system on graph classes and their inclusions (ISGCI), 2001-2014,, Accessed 2018.