圖的特徵多項式與配對多項式

Abstract

對於給定的一個簡單圖G,我們已知在圖G為森林的情況下,圖G的配對多項式恰等於特徵多項式，。但這性質不適用於任意圖。 在這篇論文中，我們給定一個公式，對於圖G的特徵多項式可以由一些圖G的子圖H的配對多項式做加減運算得到。

Let G be a simple graph. It is known that when graph G is a forest, the matching polynomial μ(G,x) is equal to the characteristic polynomial φ(G,x). But this is not true in general. In the thesis, we give a formula for φ(G,x) in terms of μ(H,x) for some subgraphs H of G.