给定度序列具有最小覆盖成本的树
The Minimum Cover Cost of a Tree with Given Degree Sequence
DOI: 10.12677/AAM.2021.107270, PDF,   
作者: 贾雁宇, 李玉瑛*, 郝艺方：太原理工大学数学学院，山西 晋中
关键词: 度序列；覆盖成本；贪婪树；Degree Sequence； Cover Cost； Greedy Tree
摘要: 图G上顶点v的覆盖成本定义为，Hvu是从v开始随机游走到达u的平均首达时间。本文研究了给定度序列树的覆盖成本，并且刻画出覆盖成本最小的树。
Abstract: The cover cost of a vertex v in G is defined as , where Hvu is the expected hitting time for random walk beginning at v to visit u. In this paper, we study the cover cost of trees and characterize the unique tree with the minimum cover cost with given degree sequence.
文章引用：贾雁宇, 李玉瑛, 郝艺方. 给定度序列具有最小覆盖成本的树[J]. 应用数学进展, 2021, 10(7): 2605-2613. https://doi.org/10.12677/AAM.2021.107270

参考文献

[1] Fischermann, M., Hoffmann, A., Rautenbach, D., Székely, L. and Volkmann, L. (2002) Wiener Index versus Maximum Degree in Trees. Discrete Applied Mathematics, 122, 127-137.
[2] Wang, H. (2008) The Extremal Values of the Wiener Index of a Tree with Given Degree Sequence. Discrete Applied Mathematics, 156, 2647-2654.
[3] Zhang, X.D., Xiang, Q.Y., Xu, L.Q. and Pan, R.Y. (2008) The Wiener Index of Trees with Given Degree Sequences. Match-Communications in Mathematical and in Computer Chemistry, 60, 623-644.
[4] Georgakopoulos, A. (2012) A Tractable Variant of Cover Time. arXiv:1206.6605.
[5] Georgakopoulos, A. and Wagner, S. (2017) Hitting Times, Cover Cost, and the Wiener Index of a Tree. Journal of Graph Theory, 84, 311-326.
[6] Li, S.C. and Wang, S.J. (2020) Extremal Cover Cost and Reverse Cover Cost of Trees with Given Segment Sequence. Discrete Mathematics, 343, 111791.
[7] Zhang, H.H. and Li, S.C. (2021) On the (Reverse) Cover Cost of Trees with Some Given Parameters. Discrete Mathematics, 344, 112226.

为你推荐