树 H_n 的道路多项式

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

某些矩阵的道路多项式

Pk（λ）表示上、下对角线元素为1，其余位置元素是0的k阶方阵的特征多项式，k≥1。如果Pk（A）≥0，k=1，2，…，A是n阶方阵，则说A是道路正矩阵。当图的邻接矩阵是道路正矩阵时，称这个图是道路正图。该文对任何k≥0．分别给出了图D、E、F晌邻接矩阵的道路多项式的表达式。这些工作是进一步研究不可约（0、1）对称矩阵的道路多项式的基础。

星S_n的道路多项式

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

圈C^n的道路多项式

１９９１年，Ｂａｐａｔ．Ｒ．Ｂ和ＬａｌＡ．Ｋ在文献［２］中猜测几乎所有的连通图都是道路正图。事实上，Ｃｎ的邻接矩阵的道路多项式计算对研究不可约（０，１）对称矩阵的道路正性有重要组合意义。该文给出了对任何ｋ≥０，圈Ｃｎ，ｎ≥４的邻接矩阵Ａ（Ｃｎ）的道路多项式Ｐｋ（Ａ（Ｃｎ），的表达式。进而证明了圈Ｃｎ，ｎ≥４，是道路正图。