树 H_n 的道路多项式

Path polynomials of Trees H n

道路多项式Ｐｋ（λ）是上，下对角线元素是１，其它元素为０的ｋ阶方阵的特征多项式，ｋ≥１；记Ｐ０（λ）≡１。连通图的邻接矩阵是不可约的（０，１）一对称矩阵。这类矩阵的道路多项式的计算有重要的组合意义。图Ｇ的邻接矩阵记作Ａ（Ｇ）。若对任何ｎ，Ｐｎ（Ａ（Ｇ））≥０，则称Ｇ是道路正图。该文给出了对任何ｋ≥０，树Ｈｎ，ｎ≥６的邻接矩阵Ａ（Ｈｎ）的道路多项式Ｐｋ（Ａ（Ｈｎ））的表达式。树Ｈｎ，ｎ≥６，是道路正图。

The path polynomial P k(λ), k≥1, is the characteristic polynomial of the tridiagonal matrix with 1′s on the super and subdiagonals and zeros elsewhere; and P 0(λ)≡1. The adjacency matrix of a connected graph is any unreduced and symmetrical (0,1) matrix. It is of combinational significance to calculate their path polynomials. Denote the adjacency matrix of a graph G by A(G); if P n(A(G))≥0, for any n, then G is called path positive graph. In this paper, we completely describe the structure formulas of path polynomials of trees H n for and k≥0 and n≥6; by the way, the tree H n, n 6, is path positive.