![](/images/graphics-bg.png)
The m-Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences
Joint Authors
McSorley, John P.
Feinsilver, Philip
Source
International Journal of Combinatorics
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-13, 13 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-01-12
Country of Publication
Egypt
No. of Pages
13
Main Subjects
Abstract EN
An m-path cover Γ={Pℓ1,Pℓ2,…,Pℓr} of a simple graph G is a set of vertex disjoint paths of G, each with ℓk≤m vertices, that span G.
With every Pℓ we associate a weight, ω(Pℓ), and define the weight of Γ to be ω(Γ)=∏k=1rω(Pℓk).
The m-path cover polynomial of G is then defined as ℙm(G)=∑Γω(Γ), where the sum is taken over all m-path covers Γ of G.
This polynomial is a specialization of the path-cover polynomial of Farrell.
We consider the m-path cover polynomial of a weighted path P(m-1,n) and find the (m+1)-term recurrence that it satisfies.
The matrix form of this recurrence yields a formula equating the trace of the recurrence matrix with the m-path cover polynomial of a suitably weighted cycle C(n).
A directed graph, T(m), the edge-weighted m-trellis, is introduced and so a third way to generate the solutions to the above (m+1)-term recurrence is presented.
We also give a model for general-term linear recurrences and time-dependent Markov chains.
American Psychological Association (APA)
McSorley, John P.& Feinsilver, Philip. 2014. The m-Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences. International Journal of Combinatorics،Vol. 2014, no. 2014, pp.1-13.
https://search.emarefa.net/detail/BIM-458034
Modern Language Association (MLA)
McSorley, John P.& Feinsilver, Philip. The m-Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences. International Journal of Combinatorics No. 2014 (2014), pp.1-13.
https://search.emarefa.net/detail/BIM-458034
American Medical Association (AMA)
McSorley, John P.& Feinsilver, Philip. The m-Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences. International Journal of Combinatorics. 2014. Vol. 2014, no. 2014, pp.1-13.
https://search.emarefa.net/detail/BIM-458034
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-458034