Abstract

A decomposition of a graph is a collection of its edge disjoint sub-graphs such that their union is . A path decomposition of a graph is a decomposition of it into paths. In this paper, we define the pendant number as the minimum number of end vertices of paths in a path decomposition of 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.

References

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, www.graphclasses.org, Accessed 2018.