On the weighted reverse cover cost of trees and unicyclic graphs with given diameter

被引:1
作者
Lv, Yan [1 ]
Chen, Zhouyang [2 ]
Wu, Tingzeng [3 ]
Zhang, Peng-Li [4 ]
机构
[1] Cent South Univ, Sch Math & Stat, New Campus, Changsha 410083, Hunan, Peoples R China
[2] Hunan Univ Finance & Econ, Sch Math & Stat, Changsha 410205, Hunan, Peoples R China
[3] Qinghai Nationalities Univ, Sch Math & Stat, Xining 810007, Qinghai, Peoples R China
[4] Shanghai Univ Int Business & Econ, Sch Stat & Informat, Shanghai 201620, Peoples R China
关键词
Trees; Unicyclic graphs; Weighted reverse cover cost; Diameter; DEGREE KIRCHHOFF INDEX; HITTING TIMES; RANDOM-WALKS; WIENER INDEX; RESISTANCE DISTANCE; INVARIANTS;
D O I
10.1016/j.amc.2024.128674
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
For a vertex x of a connected graph G = (V-G, E-G), the weighted reverse cover cost of x is proposed as RC pi G(x) = Sigma(y is an element of VG) d(y)H-yx, where d(y) denotes the degree of y and H-yx denotes the hitting time for random walk starting at y to visit x. In this paper, we first obtain the sharp lower bound of RC pi G(x) among all trees with order.. and given diameter, and then determine the sharp upper bound of RC pi G(x) among all unicyclic graphs with order n and given diameter. Furthermore, all the corresponding extremal graphs are identified.
引用
收藏
页数:17
相关论文
共 35 条
[1]  
Bapat R.B., 2010, Graphs and matrices, DOI DOI 10.1007/978-1-84882-981-7
[2]   MOLECULAR CYCLICITY AND CENTRICITY OF POLYCYCLIC GRAPHS .1. CYCLICITY BASED ON RESISTANCE DISTANCES OR RECIPROCAL DISTANCES [J].
BONCHEV, D ;
BALABAN, AT ;
LIU, XY ;
KLEIN, DJ .
INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 1994, 50 (01) :1-20
[3]  
Bondy JA, 2008, GRAPH THEORY
[4]   Chung-Yau Invariants and Graphs with Symmetric Hitting Times [J].
Chang, Xiao ;
Xu, Hao .
JOURNAL OF GRAPH THEORY, 2017, 85 (03) :691-705
[5]   Resistance distance and the normalized Laplacian spectrum [J].
Chen, Haiyan ;
Zhang, Fuji .
DISCRETE APPLIED MATHEMATICS, 2007, 155 (05) :654-661
[6]   Hitting times for random walks on subdivision and triangulation graphs [J].
Chen, Haiyan .
LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (01) :117-130
[7]   A SPANNING TREE METHOD FOR BOUNDING HITTING TIMES OF RANDOM WALKS ON GRAPHS [J].
Cogill, Randy ;
Peng, Cheng .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (03) :808-820
[8]   Wiener index of trees: Theory and applications [J].
Dobrynin, AA ;
Entringer, R ;
Gutman, I .
ACTA APPLICANDAE MATHEMATICAE, 2001, 66 (03) :211-249
[9]  
Feng LH, 2014, UTILITAS MATHEMATICA, V95, P149
[10]   FURTHER RESULTS REGARDING THE DEGREE KIRCHHOFF INDEX OF GRAPHS [J].
Feng, Lihua ;
Yu, Guihai ;
Liu, Weijun .
MISKOLC MATHEMATICAL NOTES, 2014, 15 (01) :97-108