一類圖及其線圖的Wiener指數(shù)

羅 宇， 王力工

(西北工業(yè)大學理學院應用數(shù)學系， 中國 西安 710072)

一類圖及其線圖的Wiener指數(shù)

羅 宇， 王力工

(西北工業(yè)大學理學院應用數(shù)學系， 中國 西安 710072)

Wiener指數(shù)W(G)是指一個連通圖G中所有頂點對之間的距離之和.本文定義了一類具有圈數(shù)為r，圍長為n的平面圖Gr,s,t,n，證明了對于滿足特定條件的正整數(shù)r,s,t,n，存在無窮個這樣的圖Gr,s,t,n，滿足性質W(Gr,s,t,n)=W(L(Gr,s,t,n))，這里L(Gr,s,t,n)表示圖Gr,s,t,n的線圖， 推廣了蘇曉海等人的結果.

Wiener指數(shù)；線圖；圍長

設圖G是一個具有頂點集V(G)={v1,v2,…,vn}和邊集E(G)={e1,e2,…,em}的簡單無向連通圖.圖G的頂點數(shù)n稱為圖G的階數(shù)， 也記為n(G). 圖G的線圖L(G)是指它的頂點集V(L(G))=E(G),線圖L(G)中兩個互異的頂點相鄰當且僅當在圖G中相對應的兩條邊有一個公共頂點. 一個圖G的圈數(shù)λ定義為λ(G)=m-n+1.

在本文中,作者的主要目標是找出滿足下列等式的具有特定結構的圖類，

W(L(G))=W(G) .

(1)

已知樹的Wiener指數(shù)和其線圖的Wiener指數(shù)總是不相等的[5]，對于單圈圖，除了圈圖Cn之外，均滿足W(L(G)) g0)且圈數(shù)為2的平面非二部圖滿足等式(1). 在文獻[14]中蘇曉海等人分別研究了圈數(shù)r≥7的平面二部圖和圈數(shù)r≥9的平面非二部圖滿足等式(1).在本文中，作者構造出了圍長為n和圈數(shù)r的平面圖Gr,s,t,n滿足性質(1)，并證明了這樣的圖有無窮多個，推廣了[14]的結果.

1 相關引理

為了便于計算圖的Wiener指數(shù)，先介紹兩個引理：

引理1[3]設G1和G2是任意兩個圖，v1∈V(G1)，v2∈V(G2)，且圖G是將圖G1的頂點v1和圖G2的頂點v2重疊后得到的圖，則圖G的Wiener指數(shù)為：

W(G)=W(G1)+W(G2)+(n(G1)-1)dG2(v2)+(n(G2)-1)dG1(v1).

引理2[15]設a為正整數(shù)，則不定方程x2-y2=a有解的充分必要條件是a為奇數(shù)或4 的倍數(shù).

2 主要結果

考慮如圖1所示的圖Gr,s,t,n，它的圈數(shù)為r，圍長是n(n為正整數(shù)且n≥ 3)，圖中的每個圈都是Cn，階為nr+s+t+2，對于每一組正整數(shù)r,s,t和n，Gr,s,t,n都是簡單平面圖，其線圖L(Gr,s,t,n)的具體結構見圖1，其中它的完全子圖中部分邊沒有畫出.

定理1 圖1中圖Gr,s,t,n的Wiener指數(shù)為：

A.n=2k-1時，L(Gr,s,t,n) B.n=2k時，L(Gr,s,t,n)

(2)當n=2k時，W(Gr,s,t,n)=(2k3+4k2)r2+s2+t2+3st+(k2+4k)sr+(k2+6k)rt-(k3+2k2-6k)r+2s+2t+1.

(2)當n=2k時，由Wiener指數(shù)的定義可得：W(G1)=(2k3+4k2)r2-(k3+3k2-2k)r,dG1(v)=(k2+2k)r,n(G1)=2kr+1,W(G2)=s2+t2+3st+2s+2t+1,dG2(v)=s+2t+1,n(G2)=s+t+2. 由引理1可得(2)成立．

定理2 圖1中圖Gr,s,t,n和L(Gr,s,t,n)，設ΔW(Gr,s,t,n)=W(L(Gr,s,t,n))-W(Gr,s,t,n)，則有：

定理3 對于圖1中圖Gr,s,t,n，當r,s,t,k,l均為正整數(shù)，且滿足下列條件之一，則有ΔW(Gr,s,t,n)=0，即W(L(Gr,s,t,n))=W(Gr,s,t,n).

[2s+ 2t+ 2(k-3)r+ 3]2- 4k2r2=(8k2+28)r2-8sr-(8k2+28k+4)r+1.

引入任意正整數(shù)l，上式兩邊分別減去(8kl+4l2)r2，左邊配方得

[2s+2t+2(k-3)r+3]2-[(2k+2l)r]2=(8k2-8kl-4l2+28)r2-8sr-(8k2+28k+4)r+1.

令x=2s+2t+2(k-3)r+3，y=(2k+2l)r，有

x2-y2=(8k2-8kl-4l2+28)r2-8sr-(8k2+28k+4)r+1.

顯然上式等號右邊是一個奇數(shù)，故x+y和x-y也是奇數(shù)，不妨令

其中s+t+1=(l+3)r.于是定理3(1)的結果成立.

[2s+2t+2(k-2)r+3]2- 4k2r2=(8k2+8k+20)r2-8sr-(8k2+28k+4)r+1.

引入任意正整數(shù)l，上式兩邊分別減去(8kl+4l2)r2左邊配方得到：

[2s+2t+2(k-2)r+3]2-[(2k+2l)r]2=[8k2-(8l-8)k-4l2+20]r2-8sr-(8k2+28k+20)r+1.

其中s+t+=(l+2)r.于是定理3(2)的結果成立.

推論1 當正整數(shù)n,k,r,s,t,l滿足下列條件之一，W(L(Gr,s,t,n))=W(Gr,s,t,n)成立.

(4)n=6，k=3，l=2，s=r-25,t=4r+24,r≥25是整數(shù)；

(5)n=7，k=4，l=3，s=3r-34,t=3r+33,r≥12是整數(shù)；

注當n=8，k=4 時，在0

[1] WIENER H. Structural determination of paraffin boiling points[J]. J Am Chem Soc, 1947，69(1)：17-20.

[2] DEVILLERS J, BALABAN A T. Topological indices and related descriptors in QSAR and QSPR[M]. Amsterdam: Gordon and Breach Science Publishers, 1999.

[3] DOBRYNIN A A, ENTRINGER R, GUTMAN I. Wiener index of trees: theory and applications[J].Acta Appl Math, 2001,66(3):211-249.

[4] BERTZ S H, WRIGHT W F. The graph theory approach to synthetic analysis: definition and application of molecular complexity and synthetic complexity[J]. Graph Theory Notes New York, 1998,35:32-48.

[5] BUCKLY F. Mean distance of line graphs[J]. Congr Numer, 1981,32(4):153-162.

[6] GUTMAN I. Distance of line graphs[J]. Graph Theory Notes New York, 1996,31:49-52.

[8] DOBRYNIN A A, GUTMAN I, JOVAEVIV. Bicyclic graphs and its line graphs with the same Wiener index[J]. Diskretn Analiz Issled Oper Ser 2, 1997,4(2):3-9(in Russian).

[9] 鄧漢元. 一類化學圖及其線圖的Wiener指數(shù)[J]. 湖南師范大學自然科學學報， 2009,32(3):23-26.

[10] DOBRYNIN A A, MEL’NIKOV L S. Wiener index for graphs and their line graphs with arbitrary large cyclomatic numbers[J]. Appl Math Lett, 2005,18(3):307-312.

[11] DOBRYNIN A A, MEL’NIKOV L S. Wiener index, line graphs and the cyclomatic number[J].MATCH Commun Math Comput Chem, 2005,53(1):209-214.

[12] DOBRYNIN A A, MEL’NIKOV L S. Some results on the Wiener index of iterated line graphs[J].Electron Notes Discrete Math, 2005, 22:469-475.

[13] COHEN N, DIMITROV D, KRAKOVSKI R,etal. On Wiener index of graphs and their line graphs[J].MATCH Commun Math Comput Chem, 2010,64(3):683-698.

[14] 蘇曉海，王力工. 兩類圖及其線圖的Wiener指數(shù)[J]. 山西大學學報:自然科學版, 2011,34(3):397-401.

[15] 潘承洞，潘承彪. 初等數(shù)論[M]. 北京：北京大學出版社, 1994.

(編輯 沈小玲)

Wiener Index for a Class of Graphs and Their Line Graphs

LUOYu,WANGLi-gong*

(Department of Applied Mathematics, Northwestern Polytechnical University, Xi’an 710072, China)

The Wiener indexW(G) of a connected graphGis the sum of distances among all pairs of vertices ofG. A class of planar graphGr,s,t,nwith cyclomatic numberrand girthnis defined. It is proved that for given positive integersr,s,t,n, there are infinite families of graphsGr,s,t,nhaving the propertyW(Gr,s,t,n)=W(L(Gr,s,t,n)), whereL(Gr,s,t,n) is the line graph ofGr,s,t,n. These results generalize the results of Xiaohai Su et al.

Wiener index; line graph; girth

2012-11-21

國家自然科學基金資助項目(11171273)；國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃資助項目(20120699107)

*

,E-maillgwangmath@163.com

O157.5

A

1000-2537(2014)01-0081-05