给定顶点和最大度树图的最大Sum-Balaban指标 The Maximum Sum-Balaban Index of Tree Graph with Given Vertices and Maximum Degree

doi:10.12677/AAM.2013.24019

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Advances in Applied Mathematics 应用数学进展, 2013, 2, 147-151

http://dx.doi.org/10.12677/aam.2013.24019 Published Online November 2013 (http://www.hanspub.org/journal/aam.html)

The Maximum Sum-Balaban Index of Tree Graph with

Given Vertices and Maximum Degree*

Zhif u You 1, Han Han2

1Guangdong Polytechnic Normal Un iversity, Guangzhou

2South China Normal University, Guangzhou

Email: youzhf@hotmail.com , 58 38 90363@qq.com

Received: Jul. 3rd, 2013; revised: Aug. 6th, 2013; accepted: Aug. 24th, 2013

which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract: In this paper, by using the graph operation, we determine the extremal graph which attains the

maximum Sum-Balaban index among trees with given vertices and maximum degree.

Keywords: Sum-Balaban Index; Tree Graph; Greedy Tree

给定顶点和最大度树图的最大 Sum-Balaban 指标*

游志福 1，韩函2

1广东技术师范学院，广州

2华南师范大学，广州

Email: youzhf@hotmail.com , 58 38 90363@qq.com

收稿日期：2013 年7月3日；修回日期：2013 年8月6日；录用日期：2013 年8月24 日

摘要：通过图的操作的方法，本文给出了给定顶点和最大度树图中，取得最大 Sum-Balaban 指标的

极图。

关键词：Sum-Balaban 指标；树图；Greedy 树

1. 引言

设表示简单连通图，其点集为、边集为G







EG。



表示图的最大度。G





GX表示由的点子集G

构成的引导子图。图的两个顶点和之间的距离，定义为中连接和的最短路的长度，记为Gu vGu v





du 。

 



vVG

Du duv



表示图中顶点的距离和。 Gu

记



VG n和



EG m。图的圈数G



是从中删去边，使成为无圈图的最小边数。众所周知，G G

1mn



。

连通图的 Sum-Balaban 指标[1]定义为： G

  



1uvE GGG

SJ GDu Dv







。

目前已有一些关于Sum-Balaban 指标数学方面的结果[2-4]。

*资助信息：国家自然科学基金数学天元基金(11226283)。

Open Access 147

游志福，韩函  给定顶点和最大度树图的最大 Sum-Balaban 指标

设T表示一个有根点的树。对于r





vVT，称





,dvr为的深度。中所有点最大深度称为的高，记

。

vT T

为



定义 1.1：([5])设树T有根点 u，标记 u为。对于



u1, 2,d



，T中具有 d深度的点标记为



0,,,d

u，如

果此顶点的父顶点已经标记为，使得



u

0, ,





,1, 2,

id是一个正实数且两个子顶点



0, , ,

u，



0, , ,

u满

足dd

y。上述对VT的标号定义为 T的根树标号，且根树标号的下标集记为







ST。

定义 1.2：([5])设，n



 ，。3





,Tn



是一个以为根的树，并按如下定义：





1,T由标号为的

单点构成。树的顶点集为



。当



,Tn



,,vv1

21n



 ，





,Tn



的边集为





0 1

,, n

vv01

vv 。当，

将一个叶子点，连接到的点集

1n



,Tn



v



Tn



1,





201

,, n

vv v,中度小于



的点，并使标号尽可能小。

2. 给定顶点和最大度树图的最大 Sum-Balaban 指标

树的根点为，的根点为。对

Tuv





VT 和





VT 用根树的标号法，分别得到标号集和







ST 。显

然



ST ST



。设

 



0su

SUu ，sTS

 





0suv

sSTST Vv ，则





TU 和





TV 都是树图，

且









TU TV。

定义 2.1：([5])设是树T的以 u和为端点且Pv





,duv 1



或2的一条路。和分别是的以和

为根点的两个分支。用根树标号法对和



TEPu v









VT 进行标号，分别得到





ST 和





ST 。设

  



 



,\,

stuvuv stu

TTuusSTST tSTST uuET

vusSTST tSTST uuET

 

 



。

从T到T的变换，称为







TT -变换。

引理 2.2：设是由T通过 -变换得到的图，则T













SJ TSJ T

，且成立当且仅当

。

 

SJ TSJ T





证明：设

 



0suv

Uu ，sSTST 





UVTU，

 





0su

VvsSTST v

和。若 T



VVTVT







，

则1



，1



。

对任意的

，若

 

ST ST，显然 0s



，0s



，



















0 10

,,,

Ts TsTsTsTs

DuDuUDuU DuV DuV

, (1)

且



















010

,,,

Ts TsTsTsTs

DvDvV DvU DvUDvV

 

 

,。 (2)

注意









TU TV

，且





01u

TTVU



，因此

 

Ts Ts

DuV DvU







，





01 01

Ts Ts

DuUUDvVU



 且

 

Ts Ts

DuUD vU









，





Ts Ts

DuVD vV



。

从而有















Ts TsTsTs

DuDvDuVD vV





。 (3)

类似地，



















010

,,,

Ts TsTsTsTs

DvDvUDvU DvV DvV

,， (4)



















010

,,,

Ts TsTsTsTs

DuDuV DuU DuUDuV

 

 

,。 (5)

因此，















T sTsT sTs

DuDvDuV DvV



 0。 (6)

注意到和

 

TsT s

DuV DuV











Ts Ts

DvV DvV

1

 

,，由(3)和(6)，我们有

















Ts TsTs TsTsTs

Du DvDu DvDuVDvV



 0。 (7 )

Open Access 148

游志福，韩函  给定顶点和最大度树图的最大 Sum-Balaban 指标

由(1)，(2)，(4)和(5 )，我们有

 









Ts TsTs Ts

Du DuDv Dv





。 (8)

设，

 

Ts Ts

aDu Du











Tt Tt

aDu Du





，









v，





TtT t

bDv Dv



 。由(8)，则

TsT s

bDv D





0，0ba





。 ba

设



xaa

 



，由于，则



0fx







的单调递减函数，并且是关于

 









Ts TtTs TtTs Tt

DuDuDvDvDvDvaa





 ，则

    

1111

Ts TtTsTtTsTtTs Tt

Dv DvaaDvDvDuDuDu Duaa

 



 

。

因此

   

1111

Ts TtTs TtTs TtTs Tt

Du DuDv DvDuDuDvDv

 







(9)

类似的，对于任意顶点，可以证明：

wU V









Dw Dw



。

立：这意味着下列(10)~(12)式成

对任意边













exyETU ET 



，有 V

 

TT TT

Dx DyDxDy







。 (10)

对任意边，，

 

uwETET 0s

uU









ST ST且1



，对应的边是，则有



vwE T







。 (

Ts TTs T

Dv DwDuDw





 11)

对任意边，，



vwE T0s

vV







ST ST且1



，有



Ts TTs T

Dv DwDv Dw







。 (12)

若，对于边，由(8)有



,1duv00



000

TT TT

Du DvDuDv





0



。 (13)

若，对任意



,2duv











wVT VTVT ，









Dw Dw



，因此对边









yETVT VT ，

有

 

TT TT

Dx DyDxDy







。 (14)

由(9)~(14)及Sum-Balaban 指标的定义，则









SJ TSJ T

。证毕。

满足下称为 Greedy树。定义 2.3：([5])根点为 r，给定度序列的一个树图，列条件时，

1) 对于



0hT i ，具有深度 i的任何顶点的度大于或等于具有深度 1i



的任何顶点的度。

有相同深2) 对于具度的不同顶点 w和

，且









2dx dw时，

的子顶点的最小度大于或等于的子顶

点的

相同深度的不同顶点和

最大度。

3) 对于具有，且









2dx dw



的子顶点的最小度大于或等于的子顶

时，

Open Access 149

游志福，韩函  给定顶点和最大度树图的最大 Sum-Balaban 指标

点的最大度；当

和w的位置交换时，也具有一样

完全类似文献[5] 定理11 及引理 12 的证明，我们有以下

的性质。

引理 2.4 及引理 2.5：

m-Balaban 指标。

中

引理 2.4：具有给定度序列



,,,

dd d



的所有树图中，Greedy 树取得最大 Su

证明：设T具有度序列



，且根点为。

树，则可以用图的操作变为，具有相同度序列

下面只需证明：如果T不同构一个 Greedy T



的树 T



，使得









SJ TSJ T

。

假设 Greedy树。由定义 2.3，下列三个说明成立： T不同构于一个

1) 存在





yVT使得









,,dxr dyr且









dx dy。



yVT













y dx







的一个子顶点

2d，并2) 存在具度的有相同深，且使得和的一个子顶点

满足

存在具有度的

yy

 

dx dy。

3) 相同



yVT



，且









2dy dx





，并使得



深的子顶点的最小度小于的子顶点的

最大

y

度，和y具有最小度的一，个子顶点 y



具有最大度的一个子顶点

，满足





dx dy。

对上述三种情况之一，设



uvVP使得









,,dux dvy且









v,,dxdxu 1或。和分别是2设T



u v



P以u和v为根点的两个TE分支。给定





u(或VT





VT )一个特：

于0d，任意具有



1dw且标号 1, ,

定的有根树标号法使得

1) 对为



0, d



x



0,,,d

v)的顶点 w，其子顶点被标或记为，



0, , ,,1

u



0,x

u,,,2

x，



0, , ,,1

xxdw

u…，



, ,,1

x，



v，…





, ,1

xdw

(或1

0,x



0, , ,,2

xx，1

0, ,x





)，且

记

2) 标

为u



0,1,



1, ,1

0, 和为



。

变换变为。注意到由到

y,1

则T可由



TT TT T



,的变换，将会减少满足上述三个说明的点对的个数。若

TT



，则由引，结论成立否则，重复面换，T可以变成一个具有度序列2.2理。上变



的新 greedy 树T



。由

 ，则由引理 2.2，有



SJ TSJ T

，矛盾！

结论成立。证毕。

于T



从而

是以和



,,,

dd d





1,, 1,,1,,

dd dd 引理 2.5：设 T和T分别 n

为度序列的 Greedy 树，其中



ijn

d  且j

d1，则









SJ TSJ T



。 d

的两个顶点。设





uvVP，满足







,,dux dvy

和y证明：分别是树有和T中具度 i

d且



 

,,v dx2。u

T和分别是1或uv





以

TEPu和v为根点的两个



VT (定

1) 对于 0d，任

分支。给定或



VT )一个特

的有根树标号

意具有且标号为

法使得：



1dw



0,,,d

u(或



0,,,d

v

, ,2

x，…

)的顶点，其子顶点被标记为

2) 标

wx



, 1

ddw



0,x

u, ,,1

x，



u，…，





u(或



0, ,x

v



0, ,x，



0, , ,xx

v)。

记



1, ,x0,



0, , ,,

xxdw,,1

x，v

为u



1,,1



和y为



0,1, ,1

v。

3) 标记

的子顶点为 0 ,1,



0,1,



,1,1



,1,2

u，



，…，



0, , ,,2

xxd



，



0, , ,,

u。

的顶，和由和其后继顶点引导的子

4) 对于标号为



0,1, ,1,

u点顶点 z树

T，，其中



VTVT U

 



usSTS意到在reedy树T中，u的深度大于或等于 v的深度，因个以 v

则由



TT -变换，T可

U

为根点的子树

变为，且具有度序列

T(注

)。

G此在 v

T中，存在一

同构于 u

T T





1, ,1,1, ,

ddd d

和TT







，由引理 2.2 和2.4，

则

设和



 

TSJT



。证毕



,dd





SJTSJ。

，，且对于











,,



ddd











是两个非增 r的图度序列。如果







1,2,,jn，有

1i1

i







成立，则称



优超于



。

推论 2.6：分别是以设T和T



和



为度序列的 Greedy树，并且





优超于



，则，等号成

立当

2.45及推论 2.6，则下列定理成立：

 

SJ TSJ T



且仅当TT





由引理理

。

，引 2.

Open Access 150

游志福，韩函  给定顶点和最大度树图的最大 Sum-Balaban 指标

Open Access 151













,TSJ T n，等号成立当且仅当





,TTn定理 2.7：设T是有 n个顶点，最大度为



的树，则 SJ



。

参考文献 (References)

[1] Balaban, A.T., Khadikar, P.V. and Aziz, S. (2010) Comparison of topological indices based on iterated “sum” versus “product” operations.

ommunications in Mathematical and in Computer Chemistry, 66, 273-284.

binatoria, Accepted.

l and in Computer

Iranian Journal of Mathematical Chemistry, 1, 43-67.

[2] Deng, H. (2011) On the Sum-Balaban index. MATCH C

[3] Xing , R., Zhou, B. and Grovac, A. (2012) On Sum-Balaban index. Ars Combinatoria, 104, 211-223.

[4] You, L. and Han, H. (2013) The maximum Sum-Balaban inde x of trees with given diameter. Ars Com

[5] Dong, H. and Guo, X. (2011) Character of trees with extreme Balaban index. MATCH Communications in Mathematica

Chemistry, 66, 261-272.