全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用：99美元
投递稿件

查看量下载量

相关文章

更多...

Double图的撞击时间的期望值
Expected Hitting Time of Double Graphs

DOI: 10.12677/PM.2021.114060, PP. 472-476

Keywords: Double图，撞击时间的期望值，随机游走，Randic ?矩阵
Double Graph, Expected Hitting Time, Random Walk, Randi? Matrix

Full-Text   Cite this paper   Add to My Lib

Abstract:

令G为简单连通图，DG为其double图，称图G的随机游走从点u首次到达点v所需步数的期望值为点u到点v的撞击时间的期望值。本文给出了DG和G中任意两点撞击时间的期望值之间的关系。
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.

References

[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.
https://doi.org/10.1002/jgt.22099
[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.
https://doi.org/10.1002/jgt.22029
[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.
https://doi.org/10.1016/j.jcta.2012.10.002
[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.
https://doi.org/10.4310/PAMQ.2014.v10.n3.a6
[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.
https://doi.org/10.1080/03081087.2017.1287159
[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.
https://doi.org/10.1080/03081087.2017.1395793
[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.
https://doi.org/10.1016/j.amc.2018.06.056
[11]  Munarini, E., Cippo, C.P., Scagliola, A. and Salvi, N.Z. (2008) Double Graphs. Discrete Mathematics, 308, 242-254.
https://doi.org/10.1016/j.disc.2006.11.038
[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.
https://doi.org/10.1016/j.laa.2013.06.010
[15]  Chung, F.R.K. (1997) Spectral Graph Theory. American Mathematical Society, Providence.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133