鄭學謙

(山西工程科技職業(yè)大學，山西 太原 030031)

0 引言

設圖G為簡單連通圖，其中頂點集V={v1,v2,…,vn}，邊集E={e1,e2,…,em}，最小度和最大度分別記為δ和Δ，頂點vi的度用di表示.若d1=d2=…=dn=d，則稱圖G為d-正則圖.A=(aij)n×n表示圖G的鄰接矩陣，圖G的度對角矩陣表示為D=diag{d1,d2,…,dn}，圖G的拉普拉斯矩陣表示為L=D-A，矩陣L的特征多項式|λI-L(G)|,稱為圖G的特征多項式，記作PG(λ),矩陣L的特征值稱為圖G的拉普拉斯特征值，記作0=λ1≤λ2≤…≤λn.

簡單圖G和H的并圖G∪H[1]是指具有頂點集V(G)∪V(H),邊集E(G)∪E(H)的簡單圖.簡單圖G和H的積圖G×H[1]是指具有頂點集V(G)×V(H)的簡單圖，其中(u,v)與(u′,v′)相鄰當且僅當u=u′且vv′∈E(H)或者v=v′且uu′∈E(G).

1 主要引理

等式成立當且僅當1≤i≤n，要么bi=qai,或者bi=pai.

引理3[6]G是n個頂點m條邊的簡單連通圖，最大度記為Δ,則λ2≥2m-(n-2)(Δ+1).

引理4[7]G是n個頂點m條邊的簡單連通圖，最大度和最小度分別記為Δ，δ,則

引理5[6]G是n個頂點非完全圖，λn=Δ+1,λn-1=λn-2=…=λ3,λ2=δ當且僅當G同構與下列圖之一:2K1∨Kn-2,(K1∪Kn-2)∨K1,K1,n-1,K2∪(n-2)K1,Kn-1∪K1,K1,n-2∪K1.

引理7G是n個頂點m條邊的d-正則簡單連通圖，則PL(G)(x)=(x-2d)m-nPG(x)

2 主要結論

定理1G是n個頂點m條邊的簡單連通圖，

則BH(G)≤n[(q+p)(n-1)-pq(2m+M1(G))].

則BH(G)≤n[(q+p)(n-1)-pq(2m+M1(G))]

(n-1)2≤(2m+M1(G))(BH(G))

定理3G是n個頂點m條邊的簡單連通圖，最大度和最小度分別記為Δ，δ，則

故定理成立.

定理4G同構與下列圖之一:2K1∨Kn-2,(K1∪Kn-2)∨K1,K1,n-1,K2∪(n-2)K1,Kn-1∪K1,K1,n-2∪K1,則n

證明 由引理5得，當G同構與下列圖之一:2K1∨Kn-2,(K1∪Kn-2)∨K1,K1,n-1,K2∪(n-2)K1,Kn-1∪K1,K1,n-2∪K1.λn=Δ+1,λn-1=λn-2=…=λ3,λ2=δ

由引理7得PL(G)(x)=(x-2d)m-nPG(x)

則S(L(G))={2d,…,2d,λ1,…,λn},S(G)={λ1,…,λn}