单圈图的Steiner Wiener指数的极值问题

doi:10.15960/j.cnki.issn.1007-6093.2023.03.015

运筹学学报 ›› 2023, Vol. 27 ›› Issue (3): 178-184.doi: 10.15960/j.cnki.issn.1007-6093.2023.03.015

单圈图的Steiner Wiener指数的极值问题

张杰¹^,*(), 姬燕²

1. 上海立信会计金融学院, 上海 201209
2. 山东省平阴县实验学校, 山东济南 250400

收稿日期:2019-09-18 出版日期:2023-09-15 发布日期:2023-09-14
通讯作者: 张杰 E-mail:zhangjie.sjtu@163.com
作者简介:张杰, E-mail: zhangjie.sjtu@163.com
基金资助:
国家自然科学基金(11701372);国家自然科学基金(11801371);上海市自然科学基金(16ZR1422400);上海市"人才发展资金"(2018071);上海市"扬帆计划"(19YF1435500)

Extremal problems for Steiner Wiener index of unicyclic graphs

Jie ZHANG¹^,*(), Yan JI²

1. Shanghai Lixin University of Accounting and Finance, Shanghai 201209, China
2. Pingyin Experimental School, Jinan 250400, Shandong, China

Received:2019-09-18 Online:2023-09-15 Published:2023-09-14
Contact: Jie ZHANG E-mail:zhangjie.sjtu@163.com

摘要/Abstract

摘要：

Wiener指数作为化学图论中的一个重要的化学指标, 是连通图的任意两个顶点的距离之和。Steiner Wiener指数是Wiener指数的一种推广形式, 定义为所有k个顶点的集合S的Steiner距离的和, 其中S的Steiner距离是包含S的最小连通子图的边数。本文研究了具有最小(大)Steiner Wiener指数的单圈图结构。

关键词: Steiner Wiener指数, Steiner距离, 单圈图, Wiener指数

Abstract:

Wiener index is an important chemical index in chemical graph theory, defined as the sum of distances between all pairs of vertices. A generalization of the Wiener index, called the Steiner Wiener index, takes the sum of the Steiner distances over all sets S of cardinality k. The Steiner distance of vertices in a set S is the minimum size of a connected subgraph that contain these vertices. We consider the extremal problems with respect to the Steiner Wiener index among all unicyclic graphs.

Key words: Steiner Wiener index, Steiner distance, unicyclic graphs, Wiener index

中图分类号:

O157.5

张杰, 姬燕. 单圈图的Steiner Wiener指数的极值问题[J]. 运筹学学报, 2023, 27(3): 178-184.

Jie ZHANG, Yan JI. Extremal problems for Steiner Wiener index of unicyclic graphs[J]. Operations Research Transactions, 2023, 27(3): 178-184.

图/表 4

参考文献 21

1	Bondy J A , Murty U S R . Graph Theory with Application[M]. New York: Macmillan Press, 1976.
2	Wiener H . Structural determination of paraffin boiling points[J]. Journal of the American Chemical Society, 1947, 69, 17- 20. doi: 10.1021/ja01193a005
3	Li X L , Mao Y P , Gutman I . The Steiner Wiener index of a graph[J]. Discussiones Mathematicae Graph Theory, 2016, 36, 455- 465. doi: 10.7151/dmgt.1868
4	Dankelmann P , Oellermann O R , Swart H C . The average Steiner distance of a graph[J]. Journal of Graph Theory, 1996, 22 (1): 15- 22. doi: 10.1002/(SICI)1097-0118(199605)22:1<15::AID-JGT3>3.0.CO;2-O
5	Dankelmann P , Swart H C , Oellermann O R . On the average Steiner distance of graphs with prescribed properties[J]. Discrete Applied Mathematics, 1997, 79, 91- 103. doi: 10.1016/S0166-218X(97)00035-8
6	Dankelmann P . The Steiner k-Wiener index of graphs with given minimum degree[J]. Discrete Applied Mathematics, 2019, 268, 35- 43. doi: 10.1016/j.dam.2019.05.015
7	Gutman I . On Steiner degree distance of trees[J]. Applied Mathematics and Computation, 2016, 283, 163- 167. doi: 10.1016/j.amc.2016.02.038
8	Li X L , Mao Y P , Gutman I . Inverse problem on the Steiner Wiener index[J]. Discussiones Mathematicae Graph Theory, 2018, 69, 83- 95.
9	Lu L , Huang Q , Hou J , et al. A sharp lower bound on Steiner Wiener index for trees with given diameter[J]. Discrete Mathematics, 2018, 341, 723- 731. doi: 10.1016/j.disc.2017.11.009
10	Mao Y P , Wang Z , Gutman I . Steiner Wiener index of graph products[J]. Transactions on Combinatorics, 2016, 5 (3): 39- 50.
11	Mao Y P , Wang Z , Gutman I , et al. Steiner degree distance[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2017, 78 (1): 221- 230.
12	Mao Y P , Wang Z , Gutman I , et al. Nordhaus-Gaddum-type results for the Steiner Wiener index of graphs[J]. Discrete Applied Mathematics, 2017, 219, 167- 175. doi: 10.1016/j.dam.2016.11.014
13	Zhang J , Wang H , Zhang X D . The Steiner Wiener index of trees with a given segment sequence[J]. Applied Mathematics and Computation, 2019, 344, 20- 29.
14	Zhang J , Gentry M , Wang H , et al. On the inverse Steiner Wiener problem[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2019, 82 (3): 743- 754.
15	Zhang J , Zhang G J , Wang H , et al. On extremal trees with respect to the Steiner Wiener index[J]. Discrete Mathematics Algorithms and Applications, 2019, 11 (6): 1950067. doi: 10.1142/S1793830919500678
16	Fischermann M , Hoffmann A , Rautenbach D , et al. Wiener index versus maximum degree in trees[J]. Discrete Applied Mathematics, 2002, 122, 127- 137. doi: 10.1016/S0166-218X(01)00357-2
17	Liu H , Pan X F . On the Wiener index of trees with fixed diameter[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2008, 60, 85- 94.
18	Wang H . The extremal values of the Wiener index of a tree with given degree sequence[J]. Discrete Applied Mathematics, 2008, 156, 2647- 2654. doi: 10.1016/j.dam.2007.11.005
19	Yu G H , Feng L H . On the Wiener index of unicyclic graphs with given girth[J]. Ars Combinatoria, 2010, 94, 361- 369.
20	Zhang J , Wang H , Zhang X D . The Wiener index of trees with given degree sequence and segment sequence[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2019, 81 (1): 105- 118.
21	Zhang X D , Xiang Q Y , Xu L Q , et al. The Wiener index of trees with given degree sequences[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2008, 60, 623- 644.

[1]	贾会才, 宋宏业. 基于Wiener指数和Harary指数的泛圈图的充分条件[J]. 运筹学学报, 2023, 27(3): 169-177.
[2]	余桂东, 阮征, 舒阿秀, 于涛. 单圈图的次大(拉普拉斯)分离度[J]. 运筹学学报, 2020, 24(4): 128-134.
[3]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[4]	简相国,袁西英,张曼. 单圈图和双圈图的最大无符号拉普拉斯分离度[J]. 运筹学学报, 2015, 19(2): 99-104.
[5]	梅若星, 王力工, 王陆华, 王展青. 单圈图H(p,tK_{1,m})的Laplacian谱刻画[J]. 运筹学学报, 2015, 19(1): 57-64.
[6]	邢抱花, 蔡改香. 固定直径的树的Wiener指数[J]. 运筹学学报, 2011, 15(4): 36-44.

单圈图的Steiner Wiener指数的极值问题

Extremal problems for Steiner Wiener index of unicyclic graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 21

相关文章 6

编辑推荐

Metrics

本文评价