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 Copyright © 2013 Zhifu You, Han Han. This is an open access article distributed under the Creative Commons Attribution License, 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 VG EG。 表示图 的最大度。G GX表示由 的点子集G X 构成的引导子图。图的两个顶点和 之间的距离,定义为中连接和 的最短路的长度,记为Gu vGu v v, G du 。 , GG vVG Du duv 表示图中顶点 的距离和。 Gu 记 VG n和 EG m。图 的圈数G 是从 中删去边,使 成为无圈图的最小边数。众所周知,G G 1mn 。 连通图的 Sum-Balaban 指标[1]定义为: G 1 1uvE GGG m SJ GDu Dv 。 目前已有一些关于Sum-Balaban 指标数学方面的结果[2-4]。 *资助信息:国家自然科学基金数学天元基金(11226283)。 Open Access 147 游志福,韩 函 给定顶点和最大度树图的最大 Sum-Balaban 指标 设T表示一个有根点 的树。对于r vVT,称 ,dvr为的深度。 中所有点最大深度称为 的高,记 。 vT T 为 hT 定义 1.1:([5])设树T有根点 u,标记 u为 。对于 0 u1, 2,d ,T中具有 d深度的点标记为 1 0,,,d x x u,如 果此顶点的父顶点已经标记为 ,使得 11 ,d xx u 0, , ,1, 2, i x id是一个正实数且两个子顶点 d1 0, , , x x u, d1 0, , , x y u满 足dd x y。上述对VT的标号定义为 T的根树标号,且根树标号的下标集记为 ST。 定义 1.2:([5])设 ,n Z , 。3 ,Tn 是一个以 为根的树,并按如下定义: 0 v 1,T由标号为的 单点构成。树的顶点集为 。当 0 v ,Tn 01 ,,vv1 , n v 21n , ,Tn 的边集为 0 1 ,, n vv01 vv 。当 , 将一个叶子点 ,连接到的点集 1n ,Tn 1n v Tn 1, 201 ,, n vv v,中度小于 的点,并使标号尽可能小。 2. 给定顶点和最大度树图的最大 Sum-Balaban 指标 树的根点为,的根点为 。对 u Tuv Tv u VT 和 v VT 用根树的标号法,分别得到标号集 和 u ST v ST 。显 然 u v ST ST 。设 v T 0su SUu ,sTS 0suv sSTST Vv ,则 0 TU 和 0 TV 都是树图, 且 00 TU TV。 定义 2.1:([5])设 是树T的以 u和 为端点且Pv ,duv 1 或2的一条路。 和分别是的以和 为根点的两个分支。用根树标号法对和 u Tv T TEPu v u VT v VT 进行标号,分别得到 u ST 和 v ST 。设 ,\, ,\, stuvuv stu stuvuv stu TTuusSTST tSTST uuET vusSTST tSTST uuET 。 从T到T的变换,称为 , uv TT -变换。 引理 2.2:设 是由T通过 -变换得到的图,则T , uv TT SJ TSJ T ,且 成立当且仅当 。 SJ TSJ T TT 证明:设 0suv Uu ,sSTST 10 \ u UVTU, 0su VvsSTST v 和。若 T 10 \ v VVTVT , 则1 U ,1 V 。 对任意的 s ,若 uv s ST ST,显然 0s uU ,0s vV , 0 10 ,,, Ts TsTsTsTs DuDuUDuU DuV DuV 1 , (1) 且 010 ,,, Ts TsTsTsTs DvDvV DvU DvUDvV 1 ,。 (2) 注意 00 TU TV ,且 01u TTVU ,因此 00 ,, Ts Ts DuV DvU , 01 01 ,, Ts Ts DuUUDvVU 且 11 ,, Ts Ts DuUD vU , 11 ,, Ts Ts DuVD vV 。 从而有 11 ,, Ts TsTsTs DuDvDuVD vV 0 。 (3) 类似地, 010 ,,, Ts TsTsTsTs DvDvUDvU DvV DvV 1 ,, (4) 010 ,,, Ts TsTsTsTs DuDuV DuU DuUDuV 1 ,。 (5) 因此, 11 ,, T sTsT sTs DuDvDuV DvV 0。 (6) 注意到 和 11 ,, TsT s DuV DuV 1 , Ts Ts DvV DvV 1 ,,由(3)和(6),我们有 11 ,, Ts TsTs TsTsTs Du DvDu DvDuVDvV 0。 (7 ) Open Access 148 游志福,韩 函 给定顶点和最大度树图的最大 Sum-Balaban 指标 由(1),(2),(4)和(5 ),我们有 0 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 设 11 fx x xaa ,由于 ,则 0fx f x x 的单调递减函数,并且 是关于 Ts TtTs TtTs Tt DuDuDvDvDvDvaa ,则 1111 Ts TtTsTtTsTtTs Tt Dv DvaaDvDvDuDuDu Duaa 。 因此 1111 Ts TtTs TtTs TtTs Tt Du DuDv DvDuDuDvDv (9) 类似的,对于任意顶点 ,可以证明: 11 wU V TT Dw Dw 。 立: 这意味着下列(10)~(12)式成 对任意边 1 exyETU ET 1 ,有 V 11 TT TT Dx DyDxDy 。 (10) 对任意边, , 1s uwETET 0s uU uv s ST ST且1 wU ,对应的边是 ,则有 s vwE T 11 。 ( Ts TTs T Dv DwDuDw 11) 对任意边, , 2s vwE T0s vV uv s ST ST且1 wV ,有 11 Ts TTs T Dv DwDv Dw 。 (12) 若,对于边 ,由(8)有 ,1duv00 uv 000 11 TT TT Du DvDuDv 0 。 (13) 若 ,对任意 ,2duv uv wVT VTVT , TT Dw Dw ,因此对边 uv x yETVT VT , 有 11 TT TT Dx DyDxDy 。 (14) 由(9)~(14)及Sum-Balaban 指标的定义,则 SJ TSJ T 。证毕。 满足下称为 Greedy树。 定义 2.3:([5])根点为 r,给定度序列的一个树图, 列条件时, 1) 对于 0hT i ,具有深度 i的任何顶点的度大于或等于具有深度 1i 的任何顶点的度。 有相同深2) 对于具度的不同顶点 w和 x ,且 2dx dw时, x 的子顶点的最小度大于或等于 的子顶 点的 相同深度的不同顶点 和 w 最大度。 3) 对于具有 ,且 2dx dw 的子顶点的最小度大于或等于 的子顶 w w x 时, x Open Access 149 游志福,韩 函 给定顶点和最大度树图的最大 Sum-Balaban 指标 点的最大度;当 x 和w的位置交换时,也具有一样 完全类似文献[5] 定理11 及引理 12 的证明,我们有以下 的性质。 引理 2.4 及引理 2.5: m-Balaban 指标。 中 引理 2.4:具有给定度序列 12 ,,, n dd d 的所有树图中,Greedy 树取得最大 Su 证明:设T具有度序列 ,且根点为 。 树,则 可以用图的操作变为,具有相同度序列 r 下面只需证明:如果T不同构一个 Greedy T 的树 T ,使得 SJ TSJ T 。 假设 Greedy树。由定义 2.3,下列三个说明成立: T不同构于一个 1) 存在 , x yVT使得 ,,dxr dyr且 dx dy。 , x yVT y dx x 的一个子顶点 x 2d,并2) 存在具 度的有相同深,且使 得和 的一个子顶点 满足 存在具有 度的 yy dx dy。 3) 相同 , x yVT ,且 2dy dx ,并使得 x 深的子顶点的最小度小于 的子顶点的 最大 y 度,和y具有最小度的一,个子顶点 y x 具有最大度的一个子顶点 x ,满足 dx dy。 对上述三种情况之一,设 , x y uvVP使得 ,,dux dvy且 v,,dxdxu 1或。和分别是2设T u v T uv P以u和v为根点的两个TE分支。给定 u(或VT v VT )一个特 : 于0d,任意具有 1dw且标号 1, , 定的有根树标号法使得 1) 对为 0, d x x 1 0,,,d u( x x v)的顶点 w,其子顶点被标或记为 , 1 0, , ,,1 d xx u 1 0,x u,,,2 d x, 1 0, , ,,1 d xxdw u…, , ,,1 d x, v,… , ,1 d xdw (或1 0,x v 1 0, , ,,2 d xx,1 0, ,x v ),且 记 2) 标 x 为u 0,1, v 1, ,1 v - 0, 和 为 。 变换变为。注意到由 到 y,1 则T可由 u TT TT T ,的变换,将会减少满足上述三个说明的点对的个数。若 TT ,则由引,结论成立 否则,重复 面 换,T可以变成一个具有度序列2.2理。上 变 的新 greedy 树T 。由 T ,则由引理 2.2,有 SJ TSJ T ,矛盾! 结论成立。证毕。 于T 从而 是以 和 12 ,,, n dd d 1,, 1,,1,, ij dd dd 引理 2.5:设 T和T分别 n 为度序列的 Greedy 树,其中 1 dd ijn d 且j d1,则 SJ TSJ T 。 d 的两个顶点。设 , x y uvVP,满足 ,,dux dvy x 和y证明:分别是树有 和T中具度 i d j d且 dx ,,v dx2。u T和 分别是1或uv T 以 uv TEPu和v为根点的两个 u VT (定 1) 对于 0d,任 分支。给定 或 v VT )一个特 的有根树标号 意具有 且标号为 法使得: 1dw 1 0,,,d x x u(或 1 0,,,d x x v , ,2 d x,… )的顶点 ,其子顶点被标记为 2) 标 wx , 1 ddw 1 0,x u, ,,1 d x, ,2 d x u,…, 1 u(或 1 0, ,x v 1 0, ,x, 1 0, , ,xx v)。 记 1, ,x0, 1 0, , ,, d xxdw,,1 d x,v x 为u 1,,1 和y为 0, 0,1, ,1 v。 3) 标记 x 的子顶点为 0 ,1, 0,1, ,1,1 u ,1,2 u, ,…, 1 0, , ,,2 di xxd u , 1 0, , ,, di x xd u。 的顶,和由和其后继顶点引导的子 4) 对于标号为 0,1, ,1, u点顶点 z树 i dz z T,,其中 0 \ zu VTVT U su usSTS意到在reedy树T中,u的深度大于或等于 v的深度,因个以 v 则由 , uv TT -变换,T可 0 U 为根点的子树 变为 ,且 具有度序列 v T(注 )。 G此在 v T中,存在一 同构于 u T T T 1, ,1,1, , ij ddd d n 和TT ,由引理 2.2 和2.4, 则 设 和 TSJT 。证毕 12 ,dd SJTSJ。 , ,且对于 11 nn ii ii dd 12 ,, ,, n d, n ddd 是两个非增 r的图度序列。如果 1,2,,jn,有 jj 1i1 ii i dd 成立,则称 优超于 。 推论 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. |