折叠超立方体上的随机游动

摘要

本文主要研究折叠超立方体(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.