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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 0161-1712 1687-0425 |