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

Size: px

Start display at page:

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

泉暮牛
4 years ago
Views:

1 Adance n Appled Mathematc 应用数学进展, 203, 2, Pblhed Onlne Noember 203 ( he Maxmm Sm-Balaban Index of ree raph wth en Vertce and Maxmm Degree * Zhf Yo, Han Han 2 angdong Polytechnc Normal Unerty, angzho 2 Soth Chna Normal Unerty, angzho Emal: yozhf@hotmal.com, @qq.com Receed: Jl. 3 rd, 203; reed: Ag. 6 th, 203; accepted: Ag. 24 th, 203 Copyrght 203 Zhf Yo, Han Han. h an open acce artcle dtrbted nder the Create Common Attrbton Lcene, whch permt nretrcted e, dtrbton, and reprodcton n any medm, proded the orgnal work properly cted. Abtract: In th paper, by ng the graph operaton, we determne the extremal graph whch attan the maxmm Sm-Balaban ndex among tree wth gen ertce and maxmm degree. Keyword: Sm-Balaban Index; ree raph; reedy ree * 给定顶点和最大度树图的最大 Sm-Balaban 指标游志福 2, 韩函广东技术师范学院, 广州 2 华南师范大学, 广州 Emal: yozhf@hotmal.com, @qq.com 收稿日期 :203 年 7 月 3 日 ; 修回日期 :203 年 8 月 6 日 ; 录用日期 :203 年 8 月 24 日摘要 : 通过图的操作的方法, 本文给出了给定顶点和最大度树图中, 取得最大 Sm-Balaban 指标的极图关键词 :Sm-Balaban 指标 ; 树图 ;reedy 树. 引言设表示简单连通图, 其点集为边集为 E 表示图的最大度 X 表示由的点子集 X 构成的引导子图图的两个顶点和之间的距离, 定义为中连接和的最短路的长度, 记为 d, D d, 表示图中顶点的距离和 V V 记 V n和 E m图的圈数是从中删去边, 使成为无圈图的最小边数众所周知, mn [] 连通图的 Sm-Balaban 指标定义为 : SJ m D D E 目前已有一些关于 Sm-Balaban 指标数学方面的结果 [2-4] * 资助信息 : 国家自然科学基金数学天元基金 (226283) Open Acce 47

2 游志福, 韩函给定顶点和最大度树图的最大 Sm-Balaban 指标为 h 设表示一个有根点 r 的树对于 V, 称, d r 为的深度中所有点最大深度称为的高, 记定义.:([5]) 设树有根点, 标记为 0对于 d, 2,, 中具有 d 深度的点标记为 0, x,, xd, 如果此顶点的父顶点已经标记为, 使得 x 0, x,, x, 2,, d d 是一个正实数且两个子顶点 0, x,, xd, 0, x,, yd 满 x y 上述对 V 的标号定义为的根树标号, 且根树标号的下标集记为 S 足 d d 定义.2:([5]) 设 n, Z, 3 n, 是一个以 0 为根的树, 并按如下定义 :, 单点构成树 n, 的顶点集为 0,,, n 当 2 n, n, 的边集为 0,, 0 n n, 将一个叶子点 n, 连接到 n, 的点集 0,,, n 2 2. 给定顶点和最大度树图的最大 Sm-Balaban 指标 0 由标号为的当 n, 中度小于的点, 并使标号尽可能小 V 和 S 然设 0 V0, 则 U 0 和 0 且 U 0 V 0定义 2.:([5]) 设 P 是树的以和为端点且 d, EP 为根点的两个分支用根树标号法对 V 和 V 进行标号, 分别得到 S 和 S 设树的根点为, 的根点为对 V 用根树的标号法, 分别得到标号集和 S 显 S S U S S, S S V 都是树图, 从到的变换, 称为或 2 的一条路和分别是的以和, \, S S ts S E t t, \, S S ts S E t t, - 变换, SJ SJ 引理 2.2: 设是由通过 - 变换得到的图, 则则 U 证明 : 设 U S S, U V \ U, V S S, V 0 0, 且 SJ SJ 成立当且仅当 0 和 V V \ V 若对任意的, 若 S S, 显然, V0, D D, U D, U D, V D V 0 0 0,, () 且,,, D D V D U D U D, V (2) 0 0 注意 V0, 且 V0 U, 因此 D, V0 D,, D, U D, V0 U D, U D, U, D, V D, V 且从而有 D D D, V D, V (3) 0 类似地, 因此,,,, D D U D U D V D, V, (4) 0 0,,, D D V D U D U D, V (5) 0 0,, D D D V D V 0 (6) 注意到 D, V D, V和 D, V D, V, 由 (3) 和 (6), 我们有 D D D D D, V D, V 0 (7) 48 Open Acce

3 游志福, 韩函给定顶点和最大度树图的最大 Sm-Balaban 指标由 (),(2),(4) 和 (5), 我们有 0 D D D D (8),, b D D 设 a D D, a D t D t b D D t t 由(8), 则 b a 0, ba 0 设 f x, 由于 fx 0, 则 f x 是关于 x 的单调递减函数, 并且 x xaa 有 D D D D D D a a, 则 t t t 因此 D D aa D D D D D D aa t t t t D D D D D D D D t t t t 类似的, 对于任意顶点 w U V, 可以证明 : D w D w 这意味着下列 (0)~(2) 式成立 : 对任意边 e xyeu EV, 有 D x D y D x D y (9) (0) 对任意边 we E,, S S 且 w U, 对应的边是 w E, 则有 D D w D D w 对任意边 w E 2, V0, S S 且 w V, 有若 d,, 对于边 0 0, 由 (8) 有若 d, 2, 对任意 w V V V D D w D D w D D D D ( ) (2) (3), D w D w, 因此对边 xy E V V D x D y D x D y 由 (9)~(4) 及 Sm-Balaban 指标的定义, 则 SJ SJ 证毕定义 2.3:([5]) 根点为 r, 给定度序列的一个树图, 满足下列条件时, 称为 reedy 树 ) 对于 h 0, (4), 具有深度的任何顶点的度大于或等于具有深度的任何顶点的度 2) 对于具有相同深度的不同顶点 w 和 x, 且 d x dw 2 时,x 的子顶点的最小度大于或等于 w 的子顶点的最大度相同深度的不同顶点 w 和 x d x d w 时,x 的子顶点的最小度大于或等于 w 的子顶 3) 对于具有, 且 2 Open Acce 49

4 游志福, 韩函给定顶点和最大度树图的最大 Sm-Balaban 指标点的最大度 ; 当 x 和 w 的位置交换时, 也具有一样的性质完全类似文献 [5] 中定理及引理 2 的证明, 我们有以下引理 2.4 及引理 2.5: d, d2,, dn 的所有树图中,reedy 树取得最大 Sm-Balaban 指标证明 : 设具有度序列, 且根点为 r 引理 2.4: 具有给定度序列下面只需证明 : 如果不同构一个 reedy 树, 则可以用图的操作变为, 具有相同度序列的树, 使得 SJ SJ 假设不同构于一个 reedy 树由定义 2.3, 下列三个说明成立 : ) 存在 x, y V 使得 d x, r d y, r 且 d x d y 2) 存在具度的 x, yv d y d x 2, 并 x 的一个子顶点 x dx dy 3) 存在具有相同度的 x, y V, 且 d y d x 2, 并使得 x 度, 和 y 具有最小度的一个子顶点 y, x 具有最大度的一个子顶点 x, 满足 d x dy 对上述三种情况之一, 设, VPxy 使得 d, x d, y 且,, EP 以和为根点的两个分支给定 V ( 或 V ) 一个特定的有根树标号法使得 : 满足最大有相同深, 且使得和 y 的一个子顶点 y 深的子顶点的最小度小于 y 的子顶点的 d x d x 或 2 设和分别是 ) 对于 d 0, 任意具有 dw 且标号为 0, x,, xd ( 或 0, x,, x d ) 的顶点 w, 其子顶点被标记为, 0, x,, x d, 0,x,, x d,2,, 0, x,, xd, dw ( 或,, x d,,, 0,x 0, x,, x d,,2 0, x,, xd, dw ), 且 2) 标记 x 为 0,,,和 y 为 0,,, 则可由, -变换变为注意到由到的变换, 将会减少满足上述三个说明的点对的个数若, 则由引理 2.2, 结论成立否则, 重复上面变换, 可以变成一个具有度序列的新 greedy 树由于, 则由引理 2.2, 有 SJ SJ 从而结论成立证毕, 矛盾! 引理 2.5: 设和分别是以 d, d2,, dn 和 d,, d,, d,, dn 为度序列的 reedy 树, 其中 d d d d n 且 d, 则 SJ SJ 证明 : x 和 y 分别是树中具有度 d 和 d 的两个顶点设, VPxy, 满足 d, x d, y 且 dx, dx, 或 2 和分别是 EP 以和为根点的两个分支给定 V ( 或 V ) 一个特定的有根树标号法使得 : ) 对于 d 0, 任意具有 d w 且标号为 0, x,, xd ( 或 0, x,, xd ) 的顶点 w x, 其子顶点被标记为, 0,x,, x d,, x d,,,2 ( 或 0, x,, x d,2, d, d w ) 0, x,,, 0, x,, xd, d w, x d, 0, x, 0, x,, x 2) 标记 x 为 0,,, 和 y 为 0,,, 3) 标记 x 的子顶点为 0,,,,, 0,,,,2,, 0, x,, xd, d2, 0, x,, xd, d 4) 对于标号为的顶点 z, 和由顶点 z 和其后继顶点引导的子树 0,,,, d z, V z V \, 其中 S S ( 注意到在 reedy 树中, 的深度大于或等于的深度, 因此在中, 存在一个以为根点的子树同构于 )则由, - 变换, 可变为, 且具有度序列 d,, d, d,, d n 和, 由引理 2.2 和 2.4, 则 SJ SJ SJ 证毕 n n 设 d, d 2,, d 和 d, d 2,, d, d d n n 是两个非增 r 的图度序列如果, 且对于, 2,, n, 有 d d 成立, 则称优超于推论 2.6: 设和分别是以和为度序列的 reedy 树, 并且优超于, 则 SJ SJ, 等号成立当且仅当由引理 2.4, 引理 2. 5 及推论 2.6, 则下列定理成立 : 50 Open Acce

5 游志福, 韩函给定顶点和最大度树图的最大 Sm-Balaban 指标 SJ n,, 等号成立当且仅当 n, 定理 2.7: 设是有 n 个顶点, 最大度为的树, 则 SJ 参考文献 (Reference) [] Balaban, A.., Khadkar, P.V. and Azz, S. (200) Comparon of topologcal ndce baed on terated m er prodct operaton. Iranan Jornal of Mathematcal Chemtry,, [2] Deng, H. (20) On the Sm-Balaban ndex. MACH Commncaton n Mathematcal and n Compter Chemtry, 66, [3] Xng, R., Zho, B. and roac, A. (202) On Sm-Balaban ndex. Ar Combnatora, 04, [4] Yo, L. and Han, H. (203) he maxmm Sm-Balaban ndex of tree wth gen dameter. Ar Combnatora, Accepted. [5] Dong, H. and o, X. (20) Character of tree wth extreme Balaban ndex. MACH Commncaton n Mathematcal and n Compter Chemtry, 66, Open Acce 5

离散数学

离散数学 The number of spanning trees longhuan@sjtu.edu.cn 树的刻画树 (Tree): 连通无环图树的例子 : TT 1 TT 2 TT 3 3 叶子 (leaf) 叶子 (leaf): 图 GG 中度数为 1 的顶点被称为叶子或终点 (end-vertex) 引理 : 对任意树 TT, 如果 TT 2, 则 TT 必含有至少两个终点证明 : 取 TT