标题： 有向图多项式用于计数环和路径 显示英文标题

标题： Digraph Polynomials for Counting Cycles and Paths

摘要： 许多多项式不变量定义在图上，用于编码组合信息并从代数角度研究它们。 在本文中，我们引入了有向图的环多项式和路径多项式，分别用于计数环和路径。 它们相对于基本边或顶点操作满足递推关系。 它们与其他多项式有关，并且还可以推广为双变量环多项式、双变量路径多项式和三变量环-路径多项式。 并且，一个最一般的满足此类线性递推关系的有向图多项式被递归定义，并显示可以与三变量环-路径多项式进行共约化。 我们还给出了这个多项式的显式表达式。 显示英文摘要

摘要： Many polynomial invariants are defined on graphs for encoding the combinatorial information and researching them algebraically. In this paper, we introduce the cycle polynomial and the path polynomial of directed graphs for counting cycles and paths, respectively. They satisfy recurrence relations with respect to elementary edge or vertex operations. They are related to other polynomials and can also be generalized to the bivariate cycle polynomial, the bivariate path polynomial and the trivariate cycle-path polynomial. And a most general digraph polynomial satisfying such a linear recurrence relation is recursively defined and shown to be co-reducible to the trivariate cycle-path polynomial. We also give an explicit expression of this polynomial.