四面体图与完全图字典积的平均首达时间

Expected Hitting Time of Lexicographic Products of Tetrahedral Graphs and Complete Graphs

利用多项式方法研究Johnson图J(n,3)与完全图字典积的图上随机游走。根据Hoffman多项式推导出该字典积的邻接矩阵和概率转移矩阵。进一步研究这个字典积上任意两点间的平均首达时间和电阻距离的显式公式。根据该字典积的邻接谱得到了度积基尔霍夫指数、凯梅尼常数和生成树数目。

In this paper,the random walk on the lexicographic product graphs of the Johnson graph J(n,3)and the complete graph is studied by mean of polynomial method.The adjacency matrix and probability transition matrix of the lexicographic product graph is derived according to Hoffman poly-nomial.The explicit formulas of the expected hitting time and resistance distance between any two points on the graphs are further studied.According to the adjacency spectrum of the lexicographic product graph,multiplicative degree-Kirchhoff index,Kemeny constant and the number of spanning trees are obtained.