樹的Zagreb指標的上界

李樹立

(泉州師范學院數學與計算機科學學院,福建 泉州 362000)

1 預備知識

2 主要結果

定義1對于一個連通圖G,第一類Zagreb指標M1(G)定義為

容易證明第一類Zagreb 指標也可表示為

引理1記圖G的度序列為(d1,d2,…,di,…,dj,…,dn),其中d1≥d2≥…≥dn,若圖G′的度序列為(d1,d2,…,di+1,…,dj-1,…,dn),則

M1(G)

證明由定義1可知,

M1(G′)-M1(G)=(di+1)2+(dj-1)2-

di2-dj2=2(di-dj)+2.

因為di≥dj,故di-dj≥0,則M1(G′)-M1(G)>0,引理得證.

由于n個頂點的樹有n-1條邊,由握手定理可知

kΔ+s+n-k-1=2(n-1),

即

k(Δ-1)+s=n-1.

因為

1≤s<Δ,

所以

設Sn為n個頂點的星圖,若有k個星圖Sp1,Sp2,…,Spk,則連接Spi與Spi+1的中心點,i=1,2,…,k-1,所得到的圖記為Sp1,p2+1,…,pk-1+1,pk.如圖1所示.

圖1 5個頂點的星圖S5(a)及由4個星圖S5,S4,S3,S5構造的星圖S5,5,4,5(b)Fig.1 The star S5 of five vertices (a) and the new graph S5,5,4,5 constructed by S5,S4,S3,S5 (b)

由以上分析及引理1,可得到以下定理是顯然的.

對于第一類Zagreb指標,Das等[10]得到了如下結果.

定理2[10]設T是頂點數為n,最大度為Δ的樹,則

M1(T)≤n2-3n+2(Δ+1)

等式成立當且僅當T?Sn,或T?P4.

記

g(n,Δ)=n2-3n+2(Δ+1).

下面證明我們得到的上界優于Das等[10]得到的上界.

定理3對頂點個數為n及最大度為Δ的任意樹,有f(n,Δ)≤g(n,Δ).

n-1=(n-2)·(Δ+1)-ε(Δ2-1)+

[1+ε(Δ-1)]2+n-1=(n-2)·(Δ+1)+

n-(ε-ε2)(Δ-1)2.

因為0≤ε<1,2≤Δ≤n-1,則

f(n,Δ)≤(n-2)·(Δ+1)+n=(n-4)·

(Δ+1)+n+2(Δ+1)≤(n-4)·

n+n+2(Δ+1)=n2-3n+2(Δ+1)=

g(n,Δ).

定理得證.

由定理3可知,定理1中的樹的第一類Zagreb指標的上界優于Das等[10]給出的上界,一些數值比較見表1.由表1數據可以看出f(n,Δ)≤g(n,Δ).

表1 f(n,Δ)與g(n,Δ)的一些數值比較

Tab.1 Some numerical comparisons of f(n,Δ) and g(n,Δ)

(n,Δ)f(n,Δ)g(n,Δ)f(n,Δ)/g(n,Δ)≈ (10 000,10) 119 97099 970 0221.2×10-3 (10 000,50)519 80499 970 1025.2×10-3 (10 000,100)1 019 70099 970 2021.0×10-2 (10 000,200)2 012 35099 970 4022.0×10-2 (10 000,500)5 010 34099 971 0025.0×10-2 (10 000,1000)10 010 07099 972 0021.0×10-1