圖的完全積的獨立數和獨立多項式

楊利民

（大理大學數學與計算機學院，云南大理 671003）

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

1 基本定義和引理

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

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

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

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

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

如果用S（G）記圖G 中所有穩定集合的個數，那么

定義4 圖的Merrifield-Simmons 指標，記為i（G），由Merrifield-Simmons 提出，它被定義為獨立頂點集的總的個數，包括空集〔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 中基數為k 的穩定集合的個數，并且ck（G）記補圖中階為k 的完全子圖的個數〔8-10〕，那么

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

映射? 定義如下：

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

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

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

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

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

2 主要結論

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

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

再根據引理3，于是

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

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

再根據引理4，所以就有

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

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

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

所以，根據引理3 得到風車圖的獨立多項式如下：

通過引理4 得到風車圖的Merrifield-Simmons指標如下：

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

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

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

根據定理1，于是

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

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

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

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

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

結論：不是單峰的。

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

根據定理1，那么

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

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

（2）由于

通過定理1 ，所以，

（3）根據上述結論，

推論4 假設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）根據上述發生函數，于是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的獨立多項式的系數序列是單峰的。

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

結論：序列是單峰的。

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

（2）通過定理1，于是

（3）根據上述發生函數，得到

根據定理1，那么

結論：當n≥4，它的系數序列是單峰的。

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

結論：它的系數序列不是單峰的。

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

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

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