Lollipop graphs are extremal for commute times
✍ Scribed by Johan Jonasson
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 135 KB
- Volume
- 16
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
Consider a simple random walk on a connected graph G = V E . Let C u v be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C G = max u v∈V C u v . Further, let n m be the family of connected graphs on n vertices with m edges, m ∈ n -1 n 2 , and let n = m n m be the family of all connected n-vertex graphs. It is proved that if G ∈ n m is such that C G = max H∈ n m C H then G is either a lollipop graph or a so-called double-handled lollipop graph. It is further shown, using this result, that if C G = max H∈ n C H then G is the full lollipop graph or a full double-handled lollipop graph with 2n -1 /3 vertices in the clique unless n ≤ 9 in which case G is the n-path.