Random walks on edge transitive graphs. (English) Zbl 0901.60044
The authors find explicit values for the expected hitting times between neighboring vertices of random walks on edge-transitive graphs, extending some results obtained by van Slijpe (1986), Aldous (1989), Devroye and Sbihi (1990) and Palacios (1992).
Reviewer: Liu Wen (Tianjin)
MSC:
| 60G50 | Sums of independent random variables; random walks |
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
References:
| [1] | Aldous, D., Hitting times for random walks on vertex-transitive graphs, (Math. Proc. Cambridge Phil. Soc., 106 (1989)), 179-191 · Zbl 0668.05043 |
| [2] | Aldous, D.; Fill, J., Reversible Markov chains and random walks on graphs, Book draft (1996) |
| [3] | Aleliunas, R.; Karp, R. M.; Lipton, R. J.; Lovasz, L.; Rackoff, C., Random walks, universal traversal sequences, and the complexity of maze problems, (20th Annual Symposium on Foundations of Computer Science (1979), Association for Computing Machinery: Association for Computing Machinery San Juan, PR), 218-223 |
| [4] | Bouwer, I. Z., Vertex and edge transitive, but not 1-transitive, graphs, Can. Math. Bull., 13, 231-237 (1970) · Zbl 0205.54601 |
| [5] | Buckley, F.; Harary, F., Distance in Graphs (1990), Addison-Wesley: Addison-Wesley New York · Zbl 0688.05017 |
| [6] | Devroye, L.; Sbihi, A., Random walks on highly symmetric graphs, J. Theoret. Probab., 4, 497-514 (1990) · Zbl 0711.60068 |
| [7] | Doyle, P. G.; Snell, J. L., Random Walks and Electric Networks (1984), The Mathematical Association of America: The Mathematical Association of America Washington, DC · Zbl 0583.60065 |
| [8] | Feige, U., A tight upper bound on the cover time for random walks on graphs, Ran. Str. Algorithms, 6, 51-54 (1995) · Zbl 0811.60060 |
| [9] | Folkman, J., Regular line-symmetric graphs, J. Combin. Theory, 3, 215-232 (1967) · Zbl 0158.42501 |
| [10] | Göbel, F.; Jagers, A. A., Random walks on graphs, (Stoch. Proc. Appl. Sci. Eng., 2 (1974)), 311-336 · Zbl 0296.60046 |
| [11] | Kahn, J. D.; Linial, N.; Nisan, N.; Saks, M. E., On the cover time of random walks on graphs, J. Theoret. Probab., 2, 121-128 (1989) · Zbl 0681.60064 |
| [12] | Matthews, P., Covering problems for Markov chains, Ann. Probab., 16, 1215-1228 (1988) · Zbl 0712.60076 |
| [13] | Palacios, J. L., On a result of Aleliunas et al. concerning random walks on graphs, Probab. Eng. Inform. Sci., 4, 489-492 (1990) · Zbl 1134.60370 |
| [14] | Palacios, J. L., Expected cover times of random walks on symmetric graphs, J. Theoret. Probab., 5, 597-600 (1992) · Zbl 0754.60077 |
| [15] | Renom, J. M., Tiempos esperados de llegada de paseos aleatorios en grafos altamente simétricos, (Master’s Thesis (1996), Universidad Simón Bolivar: Universidad Simón Bolivar Caracas) |
| [16] | Tetali, P., Random walks and the effective resistance of networks, J. Theoret. Probab., 4, 101-109 (1991) · Zbl 0722.60070 |
| [17] | Van Slijpe, A. R.D., Random walks on the triangular prism and other vertex transitive graphs, J. Comp. Appl. Math., 15, 383-394 (1986) · Zbl 0592.05041 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
