{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T20:59:36Z","timestamp":1782766776990,"version":"3.54.5"},"reference-count":8,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5884,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1990,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For <jats:italic>x<\/jats:italic> and <jats:italic>y<\/jats:italic> vertices of a connected graph <jats:italic>G<\/jats:italic>, let <jats:italic>T<jats:sub>G<\/jats:sub>(x, y)<\/jats:italic> denote the expected time before a random walk starting from <jats:italic>x<\/jats:italic> reaches <jats:italic>y<\/jats:italic>. We determine, for each <jats:italic>n<\/jats:italic> &gt; 0, the <jats:italic>n<\/jats:italic>\u2010vertex graph <jats:italic>G<\/jats:italic> and vertices <jats:italic>x<\/jats:italic> and <jats:italic>y<\/jats:italic> for which <jats:italic>T<jats:sub>G<\/jats:sub>(x, y)<\/jats:italic> is maximized. the extremal graph consists of a clique on \u230a(2<jats:italic>n<\/jats:italic> + 1)\/3\u230b) (or \u2308)(2<jats:sub>n<\/jats:sub> \u2212 2)\/3\u2309) vertices, including <jats:italic>x<\/jats:italic>, to which a path on the remaining vertices, ending in <jats:italic>y<\/jats:italic>, has been attached; the expected time <jats:italic>T<jats:sub>G<\/jats:sub>(x, y)<\/jats:italic> to reach <jats:italic>y<\/jats:italic> from <jats:italic>x<\/jats:italic> in this graph is approximately 4<jats:sub>n<\/jats:sub><jats:sup>3<\/jats:sup>\/27.<\/jats:p>","DOI":"10.1002\/rsa.3240010303","type":"journal-article","created":{"date-parts":[[2007,5,30]],"date-time":"2007-05-30T19:28:40Z","timestamp":1180553320000},"page":"263-276","source":"Crossref","is-referenced-by-count":78,"title":["Maximum hitting time for random walks on graphs"],"prefix":"10.1002","volume":"1","author":[{"given":"Graham","family":"Brightwell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Winkler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048271"},{"key":"e_1_2_1_3_2","unstructured":"D. J.Aldous Applications of random walks on graphs preprint 1989."},{"key":"e_1_2_1_4_2","unstructured":"D. J.Aldous Bibliography: random walks on graphs preprint 1989."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"R.Aleliunas R. M.Karp R. J.Lipton L.Lovasz andC.Rackoff Random walks universal traversal sequences and the complexity of maze problems in 20th Annual Symposium on Foundations of Computer Science San Juan Puerto Rico October1979 pp.218\u2013223.","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_2_1_6_2","volume-title":"Strength Analysis of Leveling\u2010Type Networks","author":"Borre K.","year":"1974"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"A. K.Chandra P.Raghavan W. L.Ruzzo R.SmolenskyandP.Tiwari The electrical resistance of a graph captures its commute and cover times inProceedings of the 21st Annual ACM Symposium on Theory of Computing Seattle WA May1989 pp.574\u2013586.","DOI":"10.1145\/73007.73062"},{"key":"e_1_2_1_8_2","volume-title":"Random Walks and Electrical Networks","author":"Doyle P. G.","year":"1974"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90030-0"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240010303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240010303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T09:48:56Z","timestamp":1697968136000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240010303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,9]]},"references-count":8,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1990,9]]}},"alternative-id":["10.1002\/rsa.3240010303"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240010303","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,9]]}}}