Analysis on the relation of the spectral structure of graphs to the cover times of random walks

首先研究了有限图上随机游动的覆盖时间，得到了一类特殊图的覆盖时间的显式公式，这类图被称为“蜘蛛图”。但是这种分析方法有很大的局限性，因此我们发现要想将我们的方法应用到更广泛的图类中，还需要得到更多关于离散Laplacian谱的详细信息。因此，我们决定仔细研究图的谱和几何之间的关系。因此，我们得到了一些结果的光谱散射问题，光谱共振和量子游走的行为图。

We first focused on a cover time of random walks on a finite graph, we could obtain some explicit formula for a special class of graphs, what are called “spider graphs.” However this analysis was very restricted．So we find we have to get more detailed information on spectra of discrete Laplacian in order to apply our method to a wider class of graphs. Thus we decided to study carefully the relation between spectra and geometry of graphs. We consequently obtain some results on spectral scattering problems, spectral resonance and the behaviour of quantum walks on graphs.