折叠超立方体上的随机游动
Random Walks on Folded Hypercubes
DOI: 10.12677/AAM.2019.810190, PDF,    国家自然科学基金支持
作者: 任艳芳, 杨卫华：太原理工大学数学学院，山西 太原
关键词: 随机游动；平均首达时间；基尔霍夫指数；折叠超立方体；Random Walks； Mean First-Passage Time； Kirchhoff Index； Folded Hypercube
摘要: 本文主要研究折叠超立方体(FQn)上随机游动的平均首达时间(MFPT)。当随机游动遍历图中所有顶点对时，可得到全局平均首达时间的一个显式表达，即，如果n是奇数，；如果n是偶数，。此外，还给出了折叠超立方体上随机游动的效率衡量：，以及讨论了折叠超立方体的基尔霍夫指数的计算。

In this paper, we mainly study the mean first-passage time (MFPT)) of random walks on folded hypercubes (FQn). We obtain an explicit expression of the mean first-passage time over all node pairs, that is, if n is odd, ; if n is even, . Moreover, the scaling efficiency characterizing the random walks on  is given: , and the Kirchhoff index of folded hypercubes is discussed.

文章引用：任艳芳, 杨卫华. 折叠超立方体上的随机游动[J]. 应用数学进展, 2019, 8(10): 1619-1624. https://doi.org/10.12677/AAM.2019.810190

参考文献

[1] Pearson, K. (1905) The Problem of the Random Walk. Nature, 72, 294.
[Google Scholar] [CrossRef] 
[2] Spitzer, F. (2001) Principles of Random Walk. Springer, Berlin.
[3] Woess, W. (1994) Random Walks on Infinite Graphs and Groups—A Survey on Selected Topics. Bulletin of the London Mathematical Society, 26, 1-60.
[Google Scholar] [CrossRef] 
[4] Zhang, Z., Lin, Y., Zhou, S., Wu, B. and Guan, J. (2009) Mean First-Passage Time for Random Walks on the T-Graph. New Journal of Physics, 11, Article ID: 103043.
[Google Scholar] [CrossRef] 
[5] Wu, S., Zhang, Z. and Chen, G. (2011) Random Walks on Dual Sierpinski Gaskets. The European Physical Journal, 82, 91-96.
[Google Scholar] [CrossRef] 
[6] Haynes, C.P. and Roberts, A.P. (2008) Global First-Passage Times of Fractal Lattices. Physical Review E, 78, Article ID: 041111.
[Google Scholar] [CrossRef] 
[7] Zhang, Z., Wu, B., Zhang, H., Zhou, S., Guan, J. and Wang, Z. (2010) Determining Global Mean First-Passage Time of Random Walks on Vicsek Fractals Using Eigenvalues of Laplacian Matrices. Physical Review E, 81, Article ID: 031118.
[Google Scholar] [CrossRef] 
[8] Doyle, P.G. and Snell, J.L. (2006) Random Walks and Electric Networks. The Mathematical Association of America, Oberlin.
[9] Klein, D.J. and Randic, M. (1993) Resistance Distance. Journal of Mathematical Chemistry, 12, 81-95.
[Google Scholar] [CrossRef] 
[10] El-amawy, A. and Latifi, S. (1991) Propertes and Performance of Folded Hypercubes. IEEE Transactions on Parallel and Distributed Systems, 2, 31-42.
[Google Scholar] [CrossRef] 
[11] Mirafzal, S.M. (2016) Some Other Algebraic Properties of Folded Hypercubes. Ars Combinatoria, 124, 153-156.
[12] Xu, J.M. (2001) Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, Dordrecht, Boston, London.
[13] Xu, J.M. and Ma, M.J. (2006) Cyeles-In Folded Hypercubes. Applied Mathematics Letters, 19, 140-145.
[Google Scholar] [CrossRef] 
[14] Xu, J.M. and Ma, M.J. (2010) Algebraic Properties and Panconnectivity of Folded Hypercubes. Ars Combinatoria, 95, 179-186.
[15] Zhu, H., Klein, D.J. and Lukovits, I. (1996) Extensions of the Wiener Number. Journal of Chemical Information and Computer Sciences, 36, 420-428.
[Google Scholar] [CrossRef] 
[16] Gutman, I. and Mohar, B. (1996) The Quasi-Wiener and the Kirchhoff Indices Coincide. Journal of Chemical Information and Computer Sciences, 36, 982-985.
[Google Scholar] [CrossRef] 
[17] Chen, M. and Chen, B.X. (2011) Spectra of Folded Hypercubes. Journal of East China Normal University, 61, 39-46.
[18] Chandra, A.K., Raghavan, P., Ruzzo, W.L. and Smolensky, R. (1989) The Electrical Resistance of a Graph Captures Its Commute and Cover Times. Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, 14-17 May 1989, 574-585.
[Google Scholar] [CrossRef] 
[19] Montroll, E.W. (1969) Random Walks on Lattices. III. Calculation of First-Passage Times with Application to Exciton Trapping on Photosynthetic Units. Journal of Mathematical Physics, 10, 753-765.
[Google Scholar] [CrossRef] 
[20] Agliarl, E. (2008) Exact Mean First-Passage Time on the T-Graph. Physical Review E, 77, Article ID: 011128.
[Google Scholar] [CrossRef] 
[21] Estrada, E. and Hatano, N. (2010) Topological Atomic Displacements, Kirchhoff and Wiener Indices of Molecules. Chemical Physics Letters, 486, 166-170.
[Google Scholar] [CrossRef] 
[22] Maden, A.D., Cevik, A.S., Cangul, I.N. and Das, K.C. (2013) On the Kirchhoff Matrix, a New Kirchhoff Index and the Kirchhoff Energy. Journal of Inequalities and Applications, 2013, 337.
[Google Scholar] [CrossRef] 
[23] Zhang, H., Jiang, X. and Yang, Y. (2009) Bicyclic Graphs with Extremal Kirchhoff Index. Communications in Mathematical and in Computer Chemistry, 61, 697-712.
[24] Liu, J., Pan, X., Wang, Y., et al. (2014) The Kirchhoff Index of Folded Hypercubes and Some Variet Networks. Mathematical Problems in Engineering, 3, 1-9.
[Google Scholar] [CrossRef] 
[25] Zhang, J.Y., Xiang, Y.H. and Sun, W.G. (2018) A Discrete Random Walk on the Hypercube. Physical A: Statistical Mechanics and İts Applications, 494, 1-7.
[Google Scholar] [CrossRef] 

为你推荐