Hitting times for random walks on tricyclic graphs

Abstract

AbstractLet G be a simple connected graph and [Formula: see text] Let [Formula: see text] be the expected hitting time from x to y in G and [Formula: see text] be the hitting time of G, where [Formula: see text] A tricyclic graph is a simple connected graph that the edge number equals the vertex number plus two. Let [Formula: see text] be the set of all n-vertex tricyclic graphs. In this article, we will determine the extremal graphs for hitting times among all n-vertex tricyclic graphs. Moreover, if [Formula: see text] then we will obtain sharp upper and lower bounds for [Formula: see text]

Keywords

• Hitting time
• tricyclic graph
• random walks
• 05C81
• 05C35