給定度序列的三圈圖的極值圖

楊 楊,邵燕靈

(中北大學(xué) 理學(xué)院,山西 太原 030051 )

化學(xué)圖論主要研究化學(xué)分子圖的拓?fù)洳蛔兞康男再|(zhì)與化合物的物理化學(xué)性質(zhì)[1-5].分子拓?fù)渲笖?shù)就是反映化合物的結(jié)構(gòu)特征的1種圖的不變量,它用于描述化學(xué)結(jié)構(gòu),是將分子結(jié)構(gòu)數(shù)值化的1種方式.

本文研究的所有圖均為簡(jiǎn)單連通圖[6-10].簡(jiǎn)單連通圖G的度序列為π.文中圖的的度序列均為非遞增序列π=(d0,d1,…,dn-1).Tπ表示所有度序列為π的三圈圖的集合.

1 相關(guān)引理

定義1[10-11]設(shè)g(x,y)是N×N上的二元函數(shù),如果對(duì)任意x≥y和a≥b,有g(shù)(y,a)+g(x,b)≤g(x,a)+g(y,b),當(dāng)且僅當(dāng)x=y,a=b時(shí)等號(hào)成立,則稱g(x,y)是遞增函數(shù).相似地,如果對(duì)任意x≥y和a≥b,g(y,a)+g(x,b)≥g(x,a)+g(y,b),當(dāng)且僅當(dāng)x=y,a=b等號(hào)成立,則稱g(x,y)為遞減函數(shù).

引理1[12]設(shè)g是遞增函數(shù),G∈gπ,pq,mn∈E(G)且pn,mq?E(G).設(shè)M=G-pq-mn+pn+mq,如果d(p)≥d(m)且d(n)≥d(q),則Rg(G)≤Rg(M).

引理2[12]f是遞增函數(shù),若極值圖G在gπ上使Rf最大化,G中的頂點(diǎn)記為{v1,v2,…,vn},其中v1為圖G的根點(diǎn),可滿足以下條件：

(1)0≤h(v1)≤h(v2)≤…≤h(vn),h(v)表示頂點(diǎn)v到根點(diǎn)v1的距離；

(2)d(v1)≥d(v2)≥…≥d(vn)；

(3)假設(shè)vpvq,vmvn∈E(G),vpvn,vqvm?E(G),h(vq)=h(vn)=h(vp)+1=h(vm)+1,如果p

2 主要結(jié)論

可圖三圈圖的度序列π可以分為以下幾種情況.

1)d0≥d1≥4,且dn-1=1.這樣的度序列構(gòu)成的三圈圖記為T1.

2)d0≥4>d1=d2=3,且dn-1=1.這樣的度序列構(gòu)成的三圈圖記為T2.

3)d0≥5>d1=3,d2=2且dn-1=1.這樣的度序列構(gòu)成的三圈圖記為T3.

4)d0≥6>d1=2,且dn-1=1.這樣的度序列構(gòu)成的三圈圖記為T4.

定理1設(shè)n≥6,π=(d0,d1,d2,…,dn-1)是1個(gè)可圖三圈圖的度序列,d0≥d1≥4,且dn-1=1.則對(duì)任意遞增函數(shù)f,存在1個(gè)極值圖G在T1上使Rf最大化,使得v1v2,v1v3,v1v4,v1v5,v2v3,v2v4,v2v5∈E(G)且對(duì)所有x∈V(G){v1,v2,v3,v4,v5},有d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(v5)≥d(x).

證明：根據(jù)引理2,存在1個(gè)極值圖G在T1上使Rf最大化,并把G中的頂點(diǎn)標(biāo)記為,v1為圖G的根點(diǎn).

1) 若vp-1,kvpi,vp-1,kvpj∈E(G)且i

2) 若vp-1,kvpi,vp-1,lvpj∈E(G)且k

有如下4個(gè)斷言：

由以上4個(gè)斷言可知,對(duì)任意遞增函數(shù),必存在1個(gè)極值圖G,在T1上使Rf最大化,若記v1=v01,v2=v11,v3=v12,v4=v13,v5=v14,則v1v2,v1v3,v1v4,v2v3,v2v4,v2v5∈E(G),且對(duì)所有的x∈V(G){v1,v2,v3,v4,v5},有d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(v5)≥d(x).定理證畢.d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(v5)≥d(x).

定理2設(shè)n≥6,π=(d0,d1,d2,…,dn-1)是1個(gè)可圖三圈圖的度序列,d0≥4>d1=d2=3,且dn-1=1.則對(duì)任意遞增函數(shù)f,存在1個(gè)極值圖G在T2上使Rf最大化,使得v1v2,v1v3,v1v4,v1v5,v2v3,v2v5,v3v4∈E(G) ,且對(duì)所有x∈V(G){v1,v2,v3,v4,v5},有

d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(v5)≥d(x).

家長(zhǎng)是孩子的啟蒙老師，是孩子的第一任教育者。溫馨的家庭氛圍和良好的家庭文化將對(duì)留守兒童產(chǎn)生巨大的影響。但是父母長(zhǎng)期在外，導(dǎo)致家長(zhǎng)角色弱化，父母與孩子產(chǎn)生隔閡，兒童應(yīng)有的心靈歸屬缺失。

證明：類似于與定理1的證明,我們將有以下4個(gè)斷言成立.

前3個(gè)斷言與定理1的證明類似,以下證明斷言4成立.

在極圖H2上,因?yàn)閐1=3,d2=3,有以下2種情況：

由以上4個(gè)斷言可知,若n≥6,π=(d0,d1,d2,…,dn-1)是1個(gè)可圖三圈圖的度序列,d0≥4>d1=d2=3,且dn-1=1,對(duì)任意遞增函數(shù),必存在1個(gè)極值圖G,在T2上使Rf最大化.若記v1=v01,v2=v11,v3=v12,v4=v13,v5=v14,則v1v2,v1v3,v1v4,v1v5,v2v3,v2v5,v3v4∈E(G),且對(duì)所有的x∈V(G){v1,v2,v3,v4,v5},有d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(v5)≥d(x).定理證畢.

定理3設(shè)n≥7,π=(d0,d1,d2,…,dn-1)是1個(gè)可圖三圈圖的度序列,d0≥5>d1=3,d2=2且dn-1=1.則對(duì)任意遞增函數(shù)f,存在1個(gè)極值圖G在T3上使Rf最大化,使得v1v2,v1v3,v1v4,v1v5,v1v6,v2v3,v2v4,v5v6∈E(G) ,且對(duì)所有x∈V(G){v1,v2,v3,v4,v5,v6},有d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(v5)≥d(v6)≥d(x).

證明：類似于與定理1的證明,我們將有以下4個(gè)斷言成立.

前3個(gè)斷言與定理1的證明類似,以下證明斷言4成立.

由以上4個(gè)斷言可知,若n≥7,π=(d0,d1,d2,…,dn-1)是1個(gè)可圖三圈圖的度序列,d0≥5>d1=3,d2=2且dn-1=1,則對(duì)任意遞增函數(shù),必存在1個(gè)極值圖G在T3上使Rf最大化.若記v1=v01,v2=v11,v3=v12,v4=v13,v5=v14,v6=v15,則v1v2,v1v3,v1v4,v1v5,v1v6,

v2v3,v2v4,v5v6∈E(G),且對(duì)所有的x∈V(G){v1,v2,v3,v4,v5,v6},有

d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(v5)≥d(v6)≥d(x).定理證畢.

定理4設(shè)n≥8,π=(d0,d1,d2,…,dn-1)是1個(gè)可圖三圈圖的度序列,d0≥6>d1=2,且dn-1=1.則對(duì)任意遞增函數(shù)f,存在1個(gè)極值圖G在T4上使Rf最大化,使得v1v2,v1v3,v1v4,v1v5,v1v6,v1v7,v2v3,v4v5,v6v7∈E(G) ,且對(duì)所有x∈V(G){v1,v2,v3,v4,v5,v6,v7},有d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(v5)≥d(v6)≥d(v7)≥d(x).

證明：類似于與定理1的證明,我們將有以下4個(gè)斷言成立.

前3個(gè)斷言與定理1的證明類似,以下證明斷言4成立.

由以上4個(gè)斷言可知,若n≥8,π=(d0,d1,d2,…,dn-1)是1個(gè)可圖3圈圖的度序列,d0≥6>d1=2,且dn-1=1,則對(duì)任意遞增函數(shù),必存在1個(gè)極值圖G在T4上使Rf最大化.若記v1=v01,v2=v11,v3=v12,v4=v13,v5=v14,v6=v15,v7=v16,則v1v2,v1v3,v1v4,v1v5,v1v6,v1v7,v2v3,v4v5,v6v7∈E(G),且對(duì)所有的x∈V(G){v1,v2,v3,v4,v5,v6},有

d(v1)≥d(v2)≥d(v3)≥d(v4)≥d(v5)≥d(v6)≥d(v7)≥d(x).定理證畢.

3 結(jié)語(yǔ)

給定度序列的k-圈圖的極值圖是圖論研究工作者關(guān)注的焦點(diǎn)問題之一,具有一定的理論意義,它在物理化學(xué)中預(yù)測(cè)新型化合物的物理和化學(xué)性質(zhì).給定度序列的樹、單圈圖、雙圈圖的極值圖均已經(jīng)被研究,本文在此基礎(chǔ)上研究了給定度序列的三圈圖的極值圖,將可圖三圈圖根據(jù)度序列分為4種類型,分別對(duì)這4種類型的三圈圖給出其極值圖,并拓展到具體的分子拓?fù)渲笖?shù).