匹配數(shù)為2的單圈圖最大匹配根排序

郭　強

?

匹配數(shù)為2的單圈圖最大匹配根排序

郭強

（南通大學 理學院，江蘇 南通 226019）

設(shè)是一個具有個點的簡單連通圖，圖的匹配多項式定義為。文章通過對單圈圖的匹配多項式進行計算，對匹配數(shù)為2最大匹配根進行了大小排序。

單圈圖；匹配多項式；匹配數(shù)；最大匹配根

1　引　言

自從1736年數(shù)學家Euler發(fā)表了第一篇有關(guān)圖論的文章之后便產(chǎn)生了密切聯(lián)系實際的圖論學科。多項式是處理圖的常用的代數(shù)工具，比較常見的有各種矩陣的特征多項式，為組合計數(shù)而產(chǎn)生的伴隨多項式、匹配多項式、色多項式等等。匹配多項式是這個圖上的匹配數(shù)的一種生成函數(shù)。設(shè)是一個階圖，的一個匹配是指的一個生成子圖，它的每個分支或是孤立點或是孤立邊。設(shè)為個頂點的簡單圖，其頂點集為，邊集為。圖的匹配多項式為[4]，其中表示匹配數(shù)為的數(shù)目。設(shè)表示點的鄰點的集合，表示點的度，顯然點的度就等于。表示圖的最大匹配根。匹配多項式有很多很好的性質(zhì)，它的根都是實數(shù)并且關(guān)于原點對稱；它的某種積分可以計算滿足某些條件的排列的個數(shù)[5-6]；它和圖的特征多項式之間有深刻的聯(lián)系，如在樹上匹配多項式等于特征多項式；對于一般的圖，匹配多項式是這個圖上定義的一種路樹的特征多項式的一個因子。匹配多項式和匹配的研究不僅有數(shù)學上的價值，更有化學和物理上的應用背景。

2　主要引理

引理1[1]：設(shè)是圖的生成子圖，為圖的最大匹配根，如果，則有。如果是圖的真子圖并且，則有。

圖1

引理2[2]：如果圖是有圖經(jīng)過Kelmans變換得到的，那么。

引理3[3]：假設(shè)圖和是如圖2所示的單圈圖，如果，那么，當且僅當時等號成立。

圖2

引理4[3]：在所有個點的單圈圖里()，從第一大到第四大的最大匹配根，，，。

3　結(jié)　論

可以得到

結(jié)合引理3和引理4得證。

[1]D.Cvetkovi′c,M.Doob,I.Gutman,A.Torgaˇsev,Recent Results in the Theory of Graph Spectra[J],North–Holland,Amsterdam,1988.

[2]A.K.Kelmans,On graphs with randomly deleted edges[J].Acta.Math.Acad.Sci.Hung.37(1981):77-88.

[3]Weijun.Liu,Further results on the largest matching root of unicyclic graphs[J].submitted.

[4]C.D.Godsil and I.Gutman.On the Theory of the Matching Polynomials,[J].Graph Theory,5(1981):79-87.

[5]C.D.Godsil. Hermite polynomiala and a duality relation for matching polynomials[J].Combinnatorica,1(3)(1981).257-262.

[6]C.D.Godsil.Algebraic Combinatorics[J].New York.London:Chapman and Hall,1993.

（責任編校：何俊華）

2016－03－02

郭強（1990－）湖南沅江人，南通大學碩士研究生，研究方向為代數(shù)組合。

0151

A

1673-2219（2016）05-0006-03