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

楊 楊,邵燕靈

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

化學圖論主要研究化學分子圖的拓撲不變量的性質與化合物的物理化學性質[1-5].分子拓撲指數就是反映化合物的結構特征的1種圖的不變量,它用于描述化學結構,是將分子結構數值化的1種方式.

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

1 相關引理

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

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

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

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

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

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

2 主要結論

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

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

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

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

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

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

證明：根據引理2,存在1個極值圖G在T1上使Rf最大化,并把G中的頂點標記為,v1為圖G的根點.

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

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

有如下4個斷言：

由以上4個斷言可知,對任意遞增函數,必存在1個極值圖G,在T1上使Rf最大化,若記v1=v01,v2=v11,v3=v12,v4=v13,v5=v14,則v1v2,v1v3,v1v4,v2v3,v2v4,v2v5∈E(G),且對所有的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設n≥6,π=(d0,d1,d2,…,dn-1)是1個可圖三圈圖的度序列,d0≥4>d1=d2=3,且dn-1=1.則對任意遞增函數f,存在1個極值圖G在T2上使Rf最大化,使得v1v2,v1v3,v1v4,v1v5,v2v3,v2v5,v3v4∈E(G) ,且對所有x∈V(G){v1,v2,v3,v4,v5},有

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

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

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

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

在極圖H2上,因為d1=3,d2=3,有以下2種情況：

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

定理3設n≥7,π=(d0,d1,d2,…,dn-1)是1個可圖三圈圖的度序列,d0≥5>d1=3,d2=2且dn-1=1.則對任意遞增函數f,存在1個極值圖G在T3上使Rf最大化,使得v1v2,v1v3,v1v4,v1v5,v1v6,v2v3,v2v4,v5v6∈E(G) ,且對所有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個斷言成立.

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

由以上4個斷言可知,若n≥7,π=(d0,d1,d2,…,dn-1)是1個可圖三圈圖的度序列,d0≥5>d1=3,d2=2且dn-1=1,則對任意遞增函數,必存在1個極值圖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),且對所有的x∈V(G){v1,v2,v3,v4,v5,v6},有

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

定理4設n≥8,π=(d0,d1,d2,…,dn-1)是1個可圖三圈圖的度序列,d0≥6>d1=2,且dn-1=1.則對任意遞增函數f,存在1個極值圖G在T4上使Rf最大化,使得v1v2,v1v3,v1v4,v1v5,v1v6,v1v7,v2v3,v4v5,v6v7∈E(G) ,且對所有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個斷言成立.

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

由以上4個斷言可知,若n≥8,π=(d0,d1,d2,…,dn-1)是1個可圖3圈圖的度序列,d0≥6>d1=2,且dn-1=1,則對任意遞增函數,必存在1個極值圖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),且對所有的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 結語

給定度序列的k-圈圖的極值圖是圖論研究工作者關注的焦點問題之一,具有一定的理論意義,它在物理化學中預測新型化合物的物理和化學性質.給定度序列的樹、單圈圖、雙圈圖的極值圖均已經被研究,本文在此基礎上研究了給定度序列的三圈圖的極值圖,將可圖三圈圖根據度序列分為4種類型,分別對這4種類型的三圈圖給出其極值圖,并拓展到具體的分子拓撲指數.