圖的完全積的獨(dú)立數(shù)和獨(dú)立多項(xiàng)式

楊利民

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

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

1 基本定義和引理

定義1 在圖論中，穩(wěn)定集合（或獨(dú)立集）是圖中的頂點(diǎn)集合，其中沒(méi)有兩個(gè)頂點(diǎn)是相鄰的。即，它是頂點(diǎn)的集合S 使得對(duì)于S 中每?jī)蓚€(gè)頂點(diǎn)，沒(méi)有邊聯(lián)通它們〔4〕。

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

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

叫做圖G 的獨(dú)立多項(xiàng)式〔6〕。

注：容易看出計(jì)算獨(dú)立多項(xiàng)式是NP 難問(wèn)題。

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

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

定義5 圖G 和H 的完全積，記為GΔH，它是一個(gè)新的圖，有頂點(diǎn)集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)定集合的個(gè)數(shù)，并且ck（G）記補(bǔ)圖中階為k 的完全子圖的個(gè)數(shù)〔8-10〕，那么

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

映射? 定義如下：

是H 的補(bǔ)圖。? 是一個(gè)映射。

其中α（G）是補(bǔ)圖G 中一個(gè)最大完全圖的大小。

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

其中α（G）是補(bǔ)圖G 中一個(gè)最大完全圖的大小。

引理4 存在計(jì)算恒等式如下：

2 主要結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

通過(guò)定理1 和定理2，可得

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

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

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

（3）根據(jù)上述證明過(guò)程得到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 是一個(gè)（n-2）-度正則圖，且頂點(diǎn)個(gè)數(shù)為n（偶2m），那么它的獨(dú)立多項(xiàng)式的系數(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ù)上述的獨(dú)立多項(xiàng)式，I（G；1）＝3（m1+m2+…+mq）。通過(guò)引理4，i（G）＝I（G；1）+1，所以，i（G）＝3（m1+m2+…+mq）+1。

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

（2）由于

通過(guò)定理1 ，所以，

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

推論4 假設(shè)G 是一個(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）來(lái)自定理6，令n1=n2=…=nd=n，α（Kn，n，…，n）＝max｛n，n，…，n｝＝n。

（2）來(lái)自定理6 的證明過(guò)程，于是

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

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

證明：來(lái)自推論4 的證明過(guò)程，Kn，n，…，n的獨(dú)立多項(xiàng)式的系數(shù)序列構(gòu)成如下：

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

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

（2）通過(guò)定理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ù)序列不是單峰的，所以，樹的獨(dú)立多項(xiàng)式的系數(shù)序列不是單峰的〔14〕。這樣就否定了樹的獨(dú)立多項(xiàng)式的系數(shù)是單峰的猜想。

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

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