On the average hitting times of the squares of cycles

The exact formula for the average hitting time (HT, as an abbreviation) of simple random walks from one vertex to any other vertex on the square CN2 of an N-vertex cycle graph CN was given by Chair (2014). In that paper, the author gives the expression for the even N case and the expression for the...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2022-05, Vol.313, p.18-28
Main Authors: Doi, Yoshiaki, Konno, Norio, Nakamigawa, Tomoki, Sakuma, Tadashi, Segawa, Etsuo, Shinohara, Hidehiro, Tamura, Shunya, Tanaka, Yuuho, Toyota, Kosuke
Format: Article
Language:English
Subjects:
Combinatorial analysis
Fibonacci number
Fibonacci numbers
Hitting time
Kirchhoff index
Random walk
Simple random walk
The square of a cycle
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The exact formula for the average hitting time (HT, as an abbreviation) of simple random walks from one vertex to any other vertex on the square CN2 of an N-vertex cycle graph CN was given by Chair (2014). In that paper, the author gives the expression for the even N case and the expression for the odd N case separately. In this paper, by using an elementary method different from Chair (2014), we give a much simpler single formula for the HT’s of simple random walks on CN2. Our proof is considerably short and fully combinatorial, in particular, has no-need of any spectral graph theoretical arguments. Not only the formula itself but also intermediate results through the process of our proof describe clear relations between the HT’s of simple random walks on CN2 and the Fibonacci numbers.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2022.01.001