International Journal of Mathematics and Mathematical Sciences
Volume 6 (1983), Issue 4, Pages 715-726
On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs
Department of Mathematics, The University of the West Indies, St. Augustine, Trinidad and Tobago
Received 19 October 1982
Copyright © 1983 E. J. Farrell. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Let be a graph. With every path of let us associate a weight With every spanning subgraph of consisting of paths , let us associate the weight
The path polynomial of is
where the summation is taken over all the spanning subgraphs of whose components are paths. Some basic properties of these polynomials are given. The polynomials are then used to obtain results about the minimum number of node disjoint path coverings in graphs.