路径多项式

人们可能会认为，与匹配生成多项式、独立多项式等类似，应该定义一个路径多项式，其系数是长度为的路径的数量。 虽然在文献中似乎没有定义这样的多项式，但这项工作对它们进行了定义。

路径多项式，也许是首次在此处定义，因此是多项式

其系数给出图中存在的长度为的简单路径的数量，图有个节点。

由于最短的可能路径长度为 1，因此路径多项式的多项式次数至少为 1。 特别是，，其中是图的边数。

一个图是可追踪的 当且仅当路径多项式的次数等于。 特别是，给出哈密顿路径的数量，因此一个图是可追踪的 当且仅当 。

由于非连通图中的路径计数是其连通分量中路径计数的总和，因此路径多项式在连通分量上是可加的。