SPANNING TREES AND RANDOM WALKS ON WEIGHTED GRAPHS

被引：23

作者：

Chang, Xiao ^{[1
]}

Xu, Hao ^{[1
]}

Yau, Shing-Tung ^{[2
]}

机构：

[1] Univ Pittsburgh, Dept Math, Pittsburgh, PA 15260 USA

[2] Harvard Univ, Dept Math, Cambridge, MA 02138 USA

来源：

PACIFIC JOURNAL OF MATHEMATICS | 2015年 / 273卷 / 01期

关键词：

hitting time; random walk; spanning tree; DISCRETE GREENS-FUNCTIONS;

D O I：

10.2140/pjm.2015.273.241

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Using two graph invariants arising from Chung and Yau's discrete Green's function, we derive explicit formulas and new estimates of hitting times of random walks on weighted graphs through the enumeration of spanning trees.

引用

页码：241 / 255

页数：15

共 15 条

[1] Abdullah M., 2011, ARXIV12025569
[2] Aldous D., 2014, UNFINISHED MONOGRAPH
[3] Chandra A. K., 1989, P 21 ANN ACM S THEOR, P574
[4] Chang X., 2015, PREPRINT
[5] Discrete Green's functions
Chung, F
Yau, ST
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 2000, 91 (1-2) : 191 - 214
[6] Chung Fan., 2011, Geometry and Analysis I, Advanced Lectures in Mathematics, V17, P285
[7] Georgakopoulos A, 2012, ARXIV12115689
[8] HAIYAN C, 2004, STAT PROBABIL LETT, V66, P9
[9] The hitting and cover times of random walks on finite graphs using local degree information
Ikeda, Satoshi
Kubo, Izumi
Yamashita, Masafumi
[J]. THEORETICAL COMPUTER SCIENCE, 2009, 410 (01) : 94 - 100
[10] Lovasz L, 1996, BOLYAI MATH STUD, V2, P353

← 1 2 →