On coefficients of path polynomials (Q2266721): Difference between revisions

Let \(G=(V,E)\) be a graph with vertex set V and edge set E where E is a set of 2-subsets of V. A path in G is a sequence of distinct vertices \((V_ 1,...,V_ k)\) with \(\{V_ i,V_{i+1}\}\in E\) for \(i=1,...,k-1\); a path may consist of exactly one vertex; also, a path \((V_ 1,...,V_ k)\) and its reverse \((V_ k,...,V_ 1)\) are considered the same. A path cover of G is a collection C of paths in G such that every vertex of G belongs to exactly one path in C. The weight of a path cover C is defined to be \(w^{| C|}\), and the simple path polynomial of G is defined to be \(P(G,w)=\sum w^{| C|}\) where the sum extends over all path covers C of G. Let \(P(G,w)=a_ 0w^{| V|}+a_ 1w^{| V| -1}+..\).. The author observes that the coefficient \(a_ k\) is the number of k-subsets of E which form subgraphs of G having all components paths. Thus, \(a_ 0=1\), \(a_ 1=| E|\), \(a_ 2=\left( \begin{matrix} | E| \\ 2\end{matrix} \right)\). The author is able to give formulas for \(a_ 3\), \(a_ 4\), \(a_ 5\) in terms of the number of subgraphs of G isomorphic to graphs having exactly k edges \((k=3,4,5)\) having at least one component not a path. This method would soon be worthless for computing \(a_ k\) for larger values of k. The coefficient \(a_{| V| -1}\) of w is the number of path covers of G consisting of exactly one path, so \(a_{| V| -1}\) is the number of Hamiltonian paths in G. Since determining whether G has a Hamiltonian path is probably an intractable problem, computing P(G,w) is probably intractable also.