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

我们首先研究了有限图上随机游动的覆盖时间，得到了一类特殊图的显式公式，称为“蜘蛛图”。然而，这种分析是非常有限的，所以我们发现，为了将我们的方法应用到更广泛的图类中，我们必须获得关于离散拉普拉斯谱的更详细的信息。因此，我们决定仔细研究图的谱和几何之间的关系。因此，我们在图上的谱散射问题、谱共振和量子游动的行为方面得到了一些结果。

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.