The -Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences

An -path cover of a simple graph is a set of vertex disjoint paths of , each with vertices, that span . With every we associate a weight, , and define the weight of to be . The -path cover polynomial of is then defined as where the sum is taken over all -path covers of . This polynomial is a specialization of the path-cover polynomial of Farrell. We consider the -path cover polynomial of a weighted path and find the -term recurrence that it satisfies. The matrix form of this recurrence yields a formula equating the trace of the recurrence matrix with the -path cover polynomial of a suitably weighted cycle . A directed graph, , the edge-weighted -trellis, is introduced and so a third way to generate the solutions to the above -term recurrence is presented. We also give a model for general-term linear recurrences and time-dependent Markov chains. 1. Introduction, -Path Cover Polynomial, and Notation Let be a graph with no loops or multiple edges, with vertex set . First we review some basic concepts to establish notation. A path in is a sequence of distinct vertices where each pair for is an edge. The length of a path is the number of vertices in it. Thus a path of length is a vertex and a path of length is an edge, and has length . Path begins at vertex , its first vertex, and ends at vertex , its last vertex. The path and its reverse are considered to be the same path. The set of vertices in is . Two paths and in are disjoint if . The empty path has vertices. Finally, recall that a subgraph of spans if it has the same vertex set as . Now we introduce the central concept of this paper. An -path has ; that is, it is a path of length at most for some fixed with . An -path cover of is a set of pairwise disjoint -paths of that span . Thus each satisfies , and every vertex of lies in exactly one -path; that is, is a partition of . With every -path we associate a weight, , and then the weight of is . Definition 1. The -path cover polynomial of , , is the sum of the weights of all -path covers of ; that is, where is an -path cover of . The path-cover polynomial (or path polynomial) of a graph is a specialization of the -cover polynomial of Farrell [1] where is restricted to be a path; see Farrell [2]. Thus our -path cover polynomial is a further specialization to paths of length . See also Chow [3] and D’Antona and Munarini [4]. It seems that this research is the first direct consideration of the -path cover polynomial of a graph. See McSorley et al. [5] for specialization to the case , where all classical orthogonal polynomials are generated as -path cover