|
|
双圈图中Hitting Time的极值问题
|
Abstract:
设HG(x,y)是图G上的随机游走中，从顶点x到顶点y的步数的期望值。本文主要研究一类双圈图G中φ(G)的极值问题，其中φ(G)=max{HG(x,y):x,y∈V(G)}。利用有效电阻，刻画出了在这类双圈图中，φ(G)达到极值时，相应的极图以及两点在图中的位置。
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.
| [1] | Klein, D.J. and Randi, M. (1993) Resistance Distance. Journal of Mathematical Chemistry, 12, 81-95.
https://doi.org/10.1007/BF01164627 |
| [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. https://doi.org/10.1002/jgt.22029 |
| [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. https://doi.org/10.1080/03081087.2020.1789538 |
| [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. https://doi.org/10.1080/03081087.2019.1611732 |
| [6] | Zhu, X.M. and Zhang, X.D. (2021) The Hitting Times of Random Walks on Bicyclic Graphs. Graphs and Conbinatorrics. https://doi.org/10.1007/s00373-021-02360-3 |
| [7] | Tetali, P. (1991) Random Walks and Effective Resistance of Networks. Journal of Theoretical Probability, 4, 101-109.
https://doi.org/10.1007/BF01046996 |
| [8] | Brightwell, G. and Winkler, P. (1990) Extremal Cover Times for Random Walks on Trees. Journal of Graph Theory, 14, 547-554. https://doi.org/10.1002/jgt.3190140505 |
| [9] | Lu, J., Pan, X.F. and Liu, H.Q. (2021) Bicyclic Graphs with Extremal Cover Cost. Applied Mathematics and Computation, 405, 126235. https://doi.org/10.1016/j.amc.2021.126235 |
