On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs
Let G be a graph. With every path α of G let us associate a weight wα With every spanning subgraph C of G consisting of paths α1,α2,…,αk, let us associate the weight w(C)=∏i=1kwαi. The path polynomial of G is ∑w(C), where the summation is taken over all the spanning subgraphs of G whose components a...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
1983-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1155/S0161171283000617 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832564058200473600 |
|---|---|
| author | E. J. Farrell |
| author_facet | E. J. Farrell |
| author_sort | E. J. Farrell |
| collection | DOAJ |
| description | Let G be a graph. With every path α of G let us associate a weight wα With every spanning subgraph C of G consisting of paths α1,α2,…,αk, let us associate the weight
w(C)=∏i=1kwαi.
The path polynomial of G is
∑w(C),
where the summation is taken over all the spanning subgraphs of G 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. |
| format | Article |
| id | doaj-art-65ac3b1547254f6786a94fce67377d17 |
| institution | Kabale University |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 1983-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-65ac3b1547254f6786a94fce67377d172025-02-03T01:11:50ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04251983-01-016471572610.1155/S0161171283000617On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphsE. J. Farrell0Department of Mathematics, The University of the West Indies, St. Augustine, Trinidad and TobagoLet G be a graph. With every path α of G let us associate a weight wα With every spanning subgraph C of G consisting of paths α1,α2,…,αk, let us associate the weight w(C)=∏i=1kwαi. The path polynomial of G is ∑w(C), where the summation is taken over all the spanning subgraphs of G 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.http://dx.doi.org/10.1155/S0161171283000617graph polynomialgenerating functionpath coverspanning subgraphsincorporated graphpath-to-point covering numberisland decomposition. |
| spellingShingle | E. J. Farrell On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs International Journal of Mathematics and Mathematical Sciences graph polynomial generating function path cover spanning subgraphs incorporated graph path-to-point covering number island decomposition. |
| title | On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs |
| title_full | On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs |
| title_fullStr | On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs |
| title_full_unstemmed | On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs |
| title_short | On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs |
| title_sort | on a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs |
| topic | graph polynomial generating function path cover spanning subgraphs incorporated graph path-to-point covering number island decomposition. |
| url | http://dx.doi.org/10.1155/S0161171283000617 |
| work_keys_str_mv | AT ejfarrell onaclassofpolynomialsassociatedwiththepathsinagraphanditsapplicationtominimumnodesdisjointpathcoveringsofgraphs |