Random Walks On Cubic Graph Class

Since the theory of random walk has been applied to graph theory and internet,the research of random walk on network has become a hot topic in modern probability theory.Cubic graph is a kind of well-known network topological structure.Because of its wide existence in the real society,more and more people put into the study of the dynamic behavior of random walk on it in recent years.The construction of cube is usually obtained by the Cartesian product method of small structure graph.Hypercube Q_n is one of the most general and effective network topologies,the folded hypercube FQ_n and enhanced hypercube Q_n,kis widely concerned because their properties better than Q_n .In 2018,Zhang,et al.obtained the expression of global mean first-passage time GMFPT of random walk on Q_n.Based on this,we analyze random walk on FQ_n and Q_n,k:(1)Give the explicit expressions of GMFPT of FQ_n and Q_n,k;(2)Give the efficiency measure of random walk on FQ_n: 2^n-11?(T)_n?2^n-2(n+1);(3)Give the asymptotic property of Kirchhoff index of FQ_n: K_f(FQ_n.)?N²/4(n??).In addition,we also analyze random walk on product graph C_m C_n,P_m×C_n:(4)Give the formula of GMFPT on product graph C_m C_n,P_m×C_n;(5)Give the asymptotic property of Kirchhoff index for special product graphs such as C₃×C_n,P₂×C_n,P_m×C₃,that is K_f(G₃xC_n,)?n³/8(n??), K_f(P₂×C_n)?n³/12(n??), K_f(P_m×G₃)?m³/2(n??).