郭　強(qiáng)

?

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

郭強(qiáng)

（南通大學(xué) 理學(xué)院，江蘇 南通 226019）

設(shè)是一個(gè)具有個(gè)點(diǎn)的簡(jiǎn)單連通圖，圖的匹配多項(xiàng)式定義為。文章通過(guò)對(duì)單圈圖的匹配多項(xiàng)式進(jìn)行計(jì)算，對(duì)匹配數(shù)為2最大匹配根進(jìn)行了大小排序。

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

1　引　言

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

2　主要引理

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

圖1

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

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

圖2

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

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.

（責(zé)任編校：何俊華）

2016－03－02

郭強(qiáng)（1990－）湖南沅江人，南通大學(xué)碩士研究生，研究方向?yàn)榇鷶?shù)組合。

0151

A

1673-2219（2016）05-0006-03