多扇圖中保Wiener指數(shù)的樹

王力工 樊穩(wěn)茹，張 政,2

(1.西北工業(yè)大學應(yīng)用數(shù)學系，中國 西安 710072；2.西安航空技術(shù)高等專科學?；A(chǔ)部，中國 西安 710077)

設(shè)G是一個連通的簡單圖，用V(G),E(G)分別表示圖的頂點集和邊集．圖G的頂點數(shù)即階數(shù)用n(G)表示．用d(v)表示圖G的一個頂點v的度數(shù).如果圖G的一個頂點v的度數(shù)d(v)=1，則稱頂點v為圖G的一個懸掛點．圖G的一個頂點v的距離是指圖G的頂點v到其他所有頂點的距離之和，用dG(v)表示．用G1∪G2表示兩個不相交的圖G1和G2的并圖．聯(lián)圖G1∨G2是指從并圖G1∪G2中連接圖G1的每個頂點和G2的每個頂點所得到的圖．n個頂點的路、圈和星圖分別用Pn,Cn和Sn表示．稱聯(lián)圖P1∨Pn為n+1階的扇形圖，記為Fn．稱聯(lián)圖P1∨(Pn1∪Pn2∪…∪Pnm)為n1+n2+…+nm+1階多扇圖，記為Fn1,n2,…,nm(見圖1)．設(shè)圖G是一個連通圖，用dG(u,v)表示圖G中頂點u和v的距離，即圖G中頂點u和v之間的最短路上的邊數(shù)．圖G的Wiener指數(shù)就是指圖G的任意兩點的距離之和，即

(1)

(1)中的Wiener指數(shù)W(G)一般應(yīng)用在化學中，它是化學圖論中最重要的拓撲指數(shù)之一．1947年物理化學家Harold Wiener[1]首次研究了無圈分子圖的Wiener指數(shù)，Hosoya在[2]中把Wiener指數(shù)定義為方程(1)的形式．Wiener指數(shù)自提出以后，便得到了廣泛的研究，一系列的結(jié)果相繼出現(xiàn)，有關(guān)結(jié)果參見文獻[3～13]．

本文我們考慮文獻[4]中提出的一個問題：給定一個連通圖G,G中是否存在一棵子樹T，使得W(G)=W(T)？很明顯要求圖G含有圈，并且T不一定是G的生成樹．若存在圖G中一個子樹T，使得W(G)=W(T)，則稱T為G的一個保Wiener指數(shù)的樹．本文給出了多扇圖Fn1,n2,…,nm=P1∨(Pn1∪Pn2∪…∪Pnm)中具有無窮多的保Wiener指數(shù)的子樹，推廣了徐幼專、徐立新[9]的結(jié)果．

1 相關(guān)定義和引理

定義1[7]令樹T(n,k)表示一個具有n+k個頂點的似星圖,其中一個分支頂點的度為n-1，n-1個頂點的度為1及k個頂點的度為2,且分支頂點到每個1度頂點的距離為1或2,其中k≤n-1，即樹T(n,k)是在n階星圖Sn的k條邊上各插入一個頂點后所得到的圖(見圖2)．

圖1 n1+n2+…+nm+1階多扇圖Fn1,n2,…,nm 圖2 n+k階樹T(n,k)

引理2[9]m+1階扇形圖Fm的Wiener指數(shù)為：W(Fm)=m2-m+1．

引理3[9]樹T(n,k)的Wiener指數(shù)為：W(T(n,k))=n2+(3k-2)n+(2k2-5k+1)．

引理4[4]設(shè)G1和G2分別是階為n1和n2的任意兩個圖，v1∈V(G1)，v2∈V(G2)，圖G是將圖G1的頂點v1和圖G2的頂點v2重疊后得到的圖，則圖G的Wiener指數(shù)為：

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

2 主要結(jié)果

在這一節(jié)里，我們給出了多扇圖Fn1,n2,…,nm的Wiener指數(shù)，并證明了多扇圖中具有無窮多個保Wiener指數(shù)的子樹T(l,k)．

定理1設(shè)n1+n2+…+nm=p，則p+1階多扇圖Fn1,n2,…,nm的Wiener指數(shù)為：

(2)

證對m用數(shù)學歸納法，由引理2和引理4即可證明．

定理2設(shè)p=n1+n2+…+nm.當下面兩個條件中的一個成立時，多扇圖Fn1,n2,…,nm有保Wiener指數(shù)的子樹T(l,k)，這里k≤l-1,l+k≤p+1．

(2)p=(t2+5t+m-b2+b+2)/(2b)，l=(t2+5t+m+b2-b-6bt+2)/(2b),k=2t+1，其中b和m均為正整數(shù)，t是非負整數(shù)，且b|(t2+5t+m+2)．

證假設(shè)W(Fn1,n2,…,nk+1)=W(T(l,k))，且知n1+n2+…+nm=p，由引理3和定理1可得：

p2-p+m=l2+(3k-2)l+(2k2-5k+1)．

上式兩邊乘4，配方得：

(2l+3k-2)2-(2p-1)2=k2+8k+4m-1．

令x=2l+3k-2，y=2p-1，則有

x2-y2=k2+8k+4m-1．

由不定方程知識可知，上述不定方程有解當且僅當k2+8k+4m-1為奇數(shù)或者4的倍數(shù)．因此我們討論下面兩種情況：

基于上述分析，可明確實現(xiàn)地理信息生成與地圖制圖一體化概念模型的步驟：（1）強化制圖數(shù)據(jù)內(nèi)部的數(shù)據(jù)質(zhì)量，面向制圖與空間數(shù)據(jù)建立起共同的數(shù)據(jù)標準；（2）數(shù)據(jù)生產(chǎn)平臺的建立應(yīng)以符號化為基礎(chǔ)；（3）數(shù)據(jù)管理與生產(chǎn)流程均需與生產(chǎn)目標相適應(yīng)。

(1)當k=2t為偶數(shù)時，

(x+y)(x-y)=4t2+16t+4m-1．

因x+y和x-y均為奇數(shù)，令x-y=2a-1，這里a為正整數(shù)，當(4t2+16t+4m-1)/(2a-1)是奇數(shù)時，可取

解得：

當(4t2+16t+4m-1)/(2a-1)是奇數(shù)時，則

多扇圖Fn1,n2,…,nm有保Wiener指數(shù)的子樹T(l,k)，這里p=n1+n2+…+nm，且對任意的正整數(shù)t，均有2t=k≤l-1,l+k≤p+1．

(2)當k=2t+1為奇數(shù)時，x+y和x-y均為偶數(shù)，則

(x+y)(x-y)=4t2+20t+4m+8．

令x-y=2b，這里b為正整數(shù)，當b|(t2+5t+m+2)時，可取：

解得：

故多扇圖Fn1,n2,…,nm有保Wiener指數(shù)的子樹T(l,k)，這里p=n1+n2+…+nm，其中b和m均為正整數(shù)，t是非負整數(shù)，顯然對任意的非負整數(shù)t，均有2t+1=k≤l-1,l+k≤p+1．

推論1設(shè)p=n1+n2+…+nm，當下面3個條件中的一個成立時，多扇圖Fn1,n2,…,nm有保Wiener指數(shù)的子樹T(l,k)，這里均有k≤l-1,l+k≤p+1．

(1)p=t2+4t+m,l=t2+t+m+1,k=2t，其中m和t均為正整數(shù)．

證由定理2，分別取a=1,b=1和b=2，即可證得此推論的(1)、(2)和(3)．

推論2[9]當p=t2+4t+1,l=t2+t+2,k=2t時，其中t為任意一個正整數(shù)，扇形圖Fp有保Wiener指數(shù)的子樹T(l,k)，這里k≤l-1,l+k≤p+1．

注記1從定理2可知，在多扇圖Fn1,n2,…,nm中存在無窮多的保Wiener指數(shù)的子樹T(l,k)．

參考文獻：

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

[2] HOSOYA H. Topological index, a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons[J]. Bull Chem Soc Jpn, 1971,44(9): 2332-2339.

[3] DOBRYNIN A. Branchings in trees and calculation of the Wiener index of a tree[J]. MATCH Commun Math Comput Chem, 2000, 41: 119-134.

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

[5] DOBRYNIN A, GUTMAN I, KLAV?AR S，etal. Wiener index of hexagonal systems[J]. Acta Appl Math, 2002，72(3): 247-294.

[7] 鄧漢元,王紅專. 輪形圖中保Wiener 指數(shù)的樹[J]. 湖南師范大學自然科學學報, 2005, 28(4): 1-4.

[8] 刑抱花，潘向峰.某類聯(lián)圖中保Wiener指數(shù)的樹[J]. 安慶師范學院學報：自然科學版，2008, 14(1): 3-5.

[9] 徐幼專，徐立新. 扇形圖P1∨Pm中保Wiener指數(shù)的樹[J]. 鄭州大學學報：理學版， 2006, 38(3): 32-34.

[10] 陳升平.由C6覆蓋的環(huán)狀纖維管的Wiener指數(shù)[J].湖南師范大學自然科學學報，2006， 29(3):32-35.

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

[12] 高 云，王力工.兩類聯(lián)圖中保Wiener指數(shù)的樹[J].紡織高校基礎(chǔ)科學學報，2010, 23(4):468-472.

[13] 楊 光,劉淑芳.聯(lián)圖Pm∨P2k-1中保Wiener指數(shù)的樹[J].河北北方學院學報：自然科學版，2010， 26(4):1-3,7.