Double图的撞击时间的期望值
Expected Hitting Time of Double Graphs
DOI: 10.12677/PM.2021.114060, PDF,    科研立项经费支持
作者: 孙春雨：华南理工大学数学学院，广东 广州
关键词: Double图；撞击时间的期望值；随机游走；Randic ?矩阵；Double Graph； Expected Hitting Time； Random Walk； Randi? Matrix
摘要: 令G为简单连通图，DG为其double图，称图G的随机游走从点u首次到达点v所需步数的期望值为点u到点v的撞击时间的期望值。本文给出了DG和G中任意两点撞击时间的期望值之间的关系。
Abstract: Let G be a simple connected graph and let DG be its double graph. The expected hitting time from vertices u to v is the expected value of the minimum number of jumps the random walk needs from u to v. In this paper, a relation for the expected hitting time between any two vertices of DG and G is displayed.
文章引用：孙春雨. Double图的撞击时间的期望值[J]. 理论数学, 2021, 11(4): 472-476. https://doi.org/10.12677/PM.2021.114060

参考文献

[1] Aldous, D.J. (1993) Reversible Markov Chains and Random Walks on Graphs. University of California, Berkeley.
[2] Kemeny, J.G. and Snell, J.L. (1960) Finite Markov Chains. Van Nostrand, Princeton.
[3] Chang, X. and Xu, H. (2017) Chung-Yau Invariants and Graphs with Symmetric Hitting Times. Journal of Graph Theory, 85, 691-705. [Google Scholar] [CrossRef] 
[4] Georgakopoulos, A. and Wagner, S. (2017) Hitting Times, Cover Cost, and the Wiener Index of a Tree. Journal of Graph Theory, 84, 311-326. [Google Scholar] [CrossRef] 
[5] Xu, H. and Yau, S.-T. (2013) Discrete Greens Functions and Random Walks on Graphs. Journal of Combinatorial Theory, Series A, 120, 483-499. [Google Scholar] [CrossRef] 
[6] Xu, H. and Yau, S.-T. (2014) An Explicit Formula of Hitting Times for Random Walks on Graphs. Pure and Applied Mathematics Quarterly, 10, 567-581. [Google Scholar] [CrossRef] 
[7] Lova ́sz, L. (1993) Random Walks on Graphs: A Survey. Paul Erdo ̈s is Eighty, Bolyai Society Mathematical Studies, 2, 1-46.
[8] Chen, H.Y. (2018) Hitting Times for Random Walks on Subdivision and Triangulation Graphs. Linear and Multilinear Algebra, 66, 117-130. [Google Scholar] [CrossRef] 
[9] Huang, J. and Li, S.C. (2018) Expected Hitting Times for Random Walks on Quadrilateral Graphs and Their Applications. Linear and Multilinear Algebra, 66, 2389-2408. [Google Scholar] [CrossRef] 
[10] Wang, C.Y., Guo, Z.L. and Li, S.C. (2018) Expected Hitting Times for Random Walks on the k-Triangle Graph and Their Applications. Applied Mathematics and Computation, 338, 698-710. [Google Scholar] [CrossRef] 
[11] Munarini, E., Cippo, C.P., Scagliola, A. and Salvi, N.Z. (2008) Double Graphs. Discrete Mathematics, 308, 242-254. [Google Scholar] [CrossRef] 
[12] Xin, L.W. and Yi, W.F. (2011) The Number of Spanning Trees of Double Graphs. Kragujevac Journal of Mathematics, 35, 183-190.
[13] Zhang, Z.F., Qiu, P.X., Zhang, D.H., Bian, L., Li, J.W. and Zhang, T. (2008) The Double Graph and the Complement Double Graph of a Graph. Advances in Mathematics (China), 37, 303-310.
[14] Gutman, I., Furtula, B. and Bozkurt, S. (2014) On Randic Energy. Linear Algebra and Its Applications, 422, 50-57. [Google Scholar] [CrossRef] 
[15] Chung, F.R.K. (1997) Spectral Graph Theory. American Mathematical Society, Providence.

为你推荐