楊利民

（大理大學(xué)數(shù)學(xué)與計算機學(xué)院，云南大理 671003）

通過考慮獨立多項式根的位置，Brown 等〔1〕證明了每個圖是可嵌入作為非常覆蓋圖的誘導(dǎo)子圖，這個圖的獨立多項式是單峰的。Levit 等〔2〕證明了任何良好覆蓋的蜘蛛圖的獨立多項式都是單峰的。Song 等〔3〕討論了k-樹相關(guān)圖的獨立多項式。目前有許多關(guān)于獨立多項式的文章討論單峰性，現(xiàn)在讓圖論科學(xué)家感興趣的是樹的獨立多項式的系數(shù)成單峰性的猜想。文章列舉了獨立多項式的系數(shù)是單峰的反例，否定了獨立多項式的系數(shù)是單峰的猜想以及樹的獨立多項式的系數(shù)是單峰的猜想。此外，本文還給出了許多關(guān)于圖的完全積的獨立數(shù)和獨立多項式的顯式公式以及化學(xué)圖論中許多圖的Merrifield-Simmons 指標(biāo)的顯式公式。

1 基本定義和引理

定義1 在圖論中，穩(wěn)定集合（或獨立集）是圖中的頂點集合，其中沒有兩個頂點是相鄰的。即，它是頂點的集合S 使得對于S 中每兩個頂點，沒有邊聯(lián)通它們〔4〕。

定義2 圖G 中，最大穩(wěn)定集合的大小叫做圖G 的獨立數(shù)，記為α（G）〔5〕。

定義3 如果sk記圖G 中基數(shù)為k 的穩(wěn)定集合的個數(shù)，并且α（G）是一個最大穩(wěn)定集合的大小，那么

叫做圖G 的獨立多項式〔6〕。

注：容易看出計算獨立多項式是NP 難問題。

如果用S（G）記圖G 中所有穩(wěn)定集合的個數(shù)，那么

定義4 圖的Merrifield-Simmons 指標(biāo)，記為i（G），由Merrifield-Simmons 提出，它被定義為獨立頂點集的總的個數(shù)，包括空集〔5〕。

定義5 圖G 和H 的完全積，記為GΔH，它是一個新的圖，有頂點集V（G）∪V（H）和邊集｛uv|u∈G，v∈H｝∪E（G）∪E（H）〔7〕。

｛uv|u∈Gi，v∈Gj,i≠j，1≤i，j≤t｝∪E（G1）∪E（G2）∪…∪E（Gt）。

下面是用到的一些基本引理。

引理1 如果sk記圖G 中基數(shù)為k 的穩(wěn)定集合的個數(shù)，并且ck（G）記補圖中階為k 的完全子圖的個數(shù)〔8-10〕，那么

證明：假設(shè)H（1）=圖G 中基數(shù)為k 的非空穩(wěn)定集合的集合，H（2）=補圖中階為k 的完全子圖的集合。

映射? 定義如下：

是H 的補圖。? 是一個映射。

其中α（G）是補圖G 中一個最大完全圖的大小。

證明：由定義3、引理1 和引理2，那么就有

其中α（G）是補圖G 中一個最大完全圖的大小。

引理4 存在計算恒等式如下：

2 主要結(jié)論

以下將研究圖的完全積的獨立數(shù)和獨立多項式以及獨立多項式系數(shù)的單峰性。

定理1 如果G 是圖G1，G2，…，Gn的完全積，那么

再根據(jù)引理3，于是

證明：文獻(xiàn)〔5〕給出了上述等式的歸納法證明，但是不好理解。在這里給出它的第二種簡潔證明。證明如下：

由于引理4，i（G）＝S（G）+1，所以S（G）＝i（G）-1。于是

再根據(jù)引理4，所以就有

一個風(fēng)車圖是它的邊被劃分成完全圖的邊的集合，這些完全圖有且僅有一個公共點，即，圖G 有（n1+n2+…+nd）-d+1 個頂點，G＝Kn1∪Kn2∪…∪Knd，并且Kn1∩Kn2∩…∩Knd＝K1，那么G 叫做一個風(fēng)車圖。

特別地，n∈N，令n1＝n2＝…＝nd＝n，風(fēng)車圖記為Knd。

（2）由于ck（G）= 在K1和Kn-1，n-1，…，n-1中階為k的完全子圖的個數(shù)，于是〔11-13〕

所以，根據(jù)引理3 得到風(fēng)車圖的獨立多項式如下：

通過引理4 得到風(fēng)車圖的Merrifield-Simmons指標(biāo)如下：

推論2 如果G 是一個風(fēng)車圖，那么它的獨立多項式的系數(shù)序列不是單峰的。

證明：下面舉個反例，令G＝K1210，其中n=12，d=10。根據(jù)定理2 的證明過程得到如下的系數(shù)：

通過定理1 和定理2，可得

根據(jù)定理1，于是

定理4 如果G 是一個（n-2）-度正則圖，且頂點個數(shù)為n（偶2m），那么（1）α（G）＝2；（2）I（G；x）＝2mx+mx2；（3）i（G）＝3m+1。

通過引理3，于是I（G；x）＝2mx+mx2。

（3）根據(jù)上述證明過程得到I（G；x）＝2mx+mx2，于是I（G；1）＝2m×1+m×12＝3m。再根據(jù)引理4，i（G）=I（G；1）+1，所以有i（G）=3m+1。

推論3 如果G 是一個（n-2）-度正則圖，且頂點個數(shù)為n（偶2m），那么它的獨立多項式的系數(shù)序列不是單峰的。

證明：根據(jù)定理4，I（G；x）＝2mx+mx2，它的系數(shù)序列為：2m，m。

結(jié)論：不是單峰的。

定理5 如果G 是（n1-2）-度正則圖，（n2-2）-度正則圖，…，（nq-2）-度正則圖的完全積，nj是（2mj），1≤j≤q，那么

根據(jù)定理1，那么

根據(jù)上述的獨立多項式，I（G；1）＝3（m1+m2+…+mq）。通過引理4，i（G）＝I（G；1）+1，所以，i（G）＝3（m1+m2+…+mq）+1。

定理6 假設(shè)G 是一個完全q-部圖Kn1，n2，…，nq那么

（2）由于

通過定理1 ，所以，

（3）根據(jù)上述結(jié)論，

推論4 假設(shè)G 是一個完全q-部圖Kn，n，…，n，那么

（1）α（Kn，n，…，n）＝n；

（2）I（Kn，n，…，n；x）＝q（1+x）n-q；

（3）i（Kn，n，…，n）＝q2n-q+1。

證明：（1）來自定理6，令n1=n2=…=nd=n，α（Kn，n，…，n）＝max｛n，n，…，n｝＝n。

（2）來自定理6 的證明過程，于是

（3）根據(jù)上述發(fā)生函數(shù)，于是I（Kn，n，…，n；1）＝q（1+1）n－q＝q2n－q，并且通過引理4，i（Kn，n，…，n）＝I（Kn，n，…，n；1）+1，所以i（Kn，n，…，n）＝q2n－q+1。

推論5 Kn，n，…，n的獨立多項式的系數(shù)序列是單峰的。

證明：來自推論4 的證明過程，Kn，n，…，n的獨立多項式的系數(shù)序列構(gòu)成如下：

結(jié)論：序列是單峰的。

定理7 如果G 是星形圖K1，n1，K1，n2，…，K1，nq的完全積，那么

（2）通過定理1，于是

（3）根據(jù)上述發(fā)生函數(shù)，得到

根據(jù)定理1，那么

結(jié)論：當(dāng)n≥4，它的系數(shù)序列是單峰的。

推論8 假設(shè)G 是圖K1，3，K1，3，…，K1，3的完全積，那么

結(jié)論：它的系數(shù)序列不是單峰的。

特別地，K1，3是一棵特殊的樹，I（K1，3；x）＝4x+3x2+x3，它的系數(shù)序列不是單峰的，所以，樹的獨立多項式的系數(shù)序列不是單峰的〔14〕。這樣就否定了樹的獨立多項式的系數(shù)是單峰的猜想。

綜上所述，獨立多項式的系數(shù)序列的單峰性猜想被否定。

本文中，通過轉(zhuǎn)化問題，從一般到特殊和類比三大主要的數(shù)學(xué)思想，進(jìn)一步獲得圖的完全積的獨立數(shù)和獨立多項式和技巧性地計算Merrifield-Simmons 指標(biāo)，同時否定了樹的獨立多項式的系數(shù)序列是單峰的猜想。