• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2023-07-11 04:45:14楊利民
    大理大學(xué)學(xué)報(bào) 2023年6期
    關(guān)鍵詞:單峰風(fē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ù)序列是單峰的猜想。

    猜你喜歡
    單峰風(fēng)車正則
    小風(fēng)車
    Kirchhoff方程單峰解的局部唯一性
    剩余有限Minimax可解群的4階正則自同構(gòu)
    類似于VNL環(huán)的環(huán)
    紙風(fēng)車
    瞻仰三黃風(fēng)車廟
    紅土地(2018年12期)2018-04-29 09:16:46
    小風(fēng)車,轉(zhuǎn)呀轉(zhuǎn)
    幼兒畫刊(2018年3期)2018-04-09 06:16:32
    機(jī)長(zhǎng)的約會(huì),總是安排在航站樓
    關(guān)于單峰偏好的注記
    一類平頂單峰映射的迭代
    崇礼县| 资中县| 浦县| 蕉岭县| 山西省| 翁源县| 荣昌县| 依安县| 灵寿县| 武夷山市| 阿坝县| 峨山| 岚皋县| 榆树市| 合川市| 襄城县| 邹城市| 东兰县| 龙南县| 蓝山县| 南康市| 鹿邑县| 绥中县| 北安市| 连云港市| 新密市| 云和县| 隆回县| 锦州市| 锡林浩特市| 连城县| 龙江县| 泰安市| 东方市| 龙井市| 滨州市| 新田县| 阳朔县| 互助| 囊谦县| 长垣县|