双圈图中Hitting Time的极值问题
Extremal Problems on the Hitting Time of Bicyclic Graphs
DOI: 10.12677/AAM.2021.1010379, PDF,   
作者: 史玉妙, 桂雪瑶：浙江师范大学数学与计算机科学学院，浙江 金华；王华平：江西师范大学数学与统计学院，江西 南昌
关键词: Hitting Time；有效电阻；双圈图；Hitting Time； Effective Resistance； Bicyclic Graph
摘要: 设HG(x,y)是图G上的随机游走中，从顶点x到顶点y的步数的期望值。本文主要研究一类双圈图G中φ(G)的极值问题，其中φ(G)=max{HG(x,y):x,y∈V(G)}。利用有效电阻，刻画出了在这类双圈图中，φ(G)达到极值时，相应的极图以及两点在图中的位置。
Abstract: Let HG(x,y) be the expected steps from vertex x to vertex y on random walk on graph G. In this paper, we will consider the extremal values of φ(G) in bicyclic graphs G, where φ(G)=max{HG(x,y):x,y∈V(G)}. By using effective resistance, we characterize the corresponding extremal graph and the position of two vertices in the graph when φ(G) reaches the extremum.
文章引用：史玉妙, 桂雪瑶, 王华平. 双圈图中Hitting Time的极值问题[J]. 应用数学进展, 2021, 10(10): 3592-3600. https://doi.org/10.12677/AAM.2021.1010379

参考文献

[1] Klein, D.J. and Randi, M. (1993) Resistance Distance. Journal of Mathematical Chemistry, 12, 81-95. [Google Scholar] [CrossRef] 
[2] Georgakopoulos, A. and Wagner, S. (2017) Hitting Times, Cover Cost, and the Wiener Index of a Tree. Journal of Graph Theory, 84, 311-326. [Google Scholar] [CrossRef] 
[3] Aldous, D.J. (1993) Reversible Markov Chains and Random Walks on Graphs. University of California, Berkeley.
[4] Zhang, H.H. and Li, S.C. (2020) Extremal Hitting Times of Trees with Some Given Paramaters. Linear and Multilinear Algebra. [Google Scholar] [CrossRef] 
[5] Zhu, X.M. and Zhang, X.D. (2019) The Hitting Time of Random Walk on Unicyclic Graphs. Linear and Multilinear Algebra, 69, 573-592. [Google Scholar] [CrossRef] 
[6] Zhu, X.M. and Zhang, X.D. (2021) The Hitting Times of Random Walks on Bicyclic Graphs. Graphs and Conbinatorrics. [Google Scholar] [CrossRef] 
[7] Tetali, P. (1991) Random Walks and Effective Resistance of Networks. Journal of Theoretical Probability, 4, 101-109. [Google Scholar] [CrossRef] 
[8] Brightwell, G. and Winkler, P. (1990) Extremal Cover Times for Random Walks on Trees. Journal of Graph Theory, 14, 547-554. [Google Scholar] [CrossRef] 
[9] Lu, J., Pan, X.F. and Liu, H.Q. (2021) Bicyclic Graphs with Extremal Cover Cost. Applied Mathematics and Computation, 405, 126235. [Google Scholar] [CrossRef] 

为你推荐