The hitting time of random walk on unicyclic graphs

Abstract

Let $H_G(x,y)$ be the hitting time from one vertex x to another vertex y on a simple graph G, which is the expected number of steps before a simple random walk starting from a vertex x reaches a vertex y in G, and $\varphi \left(G\right)$ be the maximum value of the hitting time $H_G(x,y)$ for any two vertices x,y in G. In this paper, we explicate how the maximum value $\varphi \left(G\right)$ alters after graph grafting, which are further used to present sharp upper and lower bounds for $\varphi \left(G\right)$ among all unicyclic graphs. Moreover, all extremal graphs which attached the values are determined.

Keywords:

• Hitting time
• unicyclic graph
• random walk
• graph grafting

AMS Classifications:

• 05C81
• 05C35

Acknowledgments

The authors would like to appreciate the anonymous referee for constructive suggestions to an earlier version of this manuscript, which results in a great improvement.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by the Montenegrin-Chinese Science and Technology Cooperation Project (No.3-12); the National Natural Science Foundation of China [grant number 11531001]; the Joint NSFC-ISF Research Program (jointly funded by the National Natural Science Foundation of China and the Israel Science Foundation) [grant number 11561141001].