{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T22:34:58Z","timestamp":1776983698300,"version":"3.51.4"},"reference-count":10,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2006,10,6]],"date-time":"2006-10-06T00:00:00Z","timestamp":1160092800000},"content-version":"vor","delay-in-days":5818,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1990,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>C<jats:sub>\u03bd<\/jats:sub><\/jats:italic>(<jats:italic>T<\/jats:italic>) denote the \u201ccover time\u201d of the tree <jats:italic>T<\/jats:italic> from the vertex <jats:italic>v<\/jats:italic>, that is, the expected number of steps before a random walk starting at <jats:italic>v<\/jats:italic> hits every vertex of <jats:italic>T.<\/jats:italic> Asymptotic lower bounds for <jats:italic>C<jats:sub>\u03bd<\/jats:sub><\/jats:italic>(<jats:italic>T<\/jats:italic>) (for <jats:italic>T<\/jats:italic> a tree on <jats:italic>n<\/jats:italic> vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2<jats:italic>n<\/jats:italic> In <jats:italic>n<\/jats:italic>) by showing that <jats:italic>C<jats:sub>\u03bd<\/jats:sub><\/jats:italic>(<jats:italic>T<\/jats:italic>) is minimized when <jats:italic>T<\/jats:italic> is a star and <jats:italic>v<\/jats:italic> is one of its leaves.<\/jats:p><jats:p>In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).<\/jats:p>","DOI":"10.1002\/jgt.3190140505","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T12:50:53Z","timestamp":1180183853000},"page":"547-554","source":"Crossref","is-referenced-by-count":25,"title":["Extremal cover times for random walks on trees"],"prefix":"10.1002","volume":"14","author":[{"given":"Graham","family":"Brightwell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Winkler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,6]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048271"},{"key":"e_1_2_1_3_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. 20th Annual Symposium on Foundations of Computer Science San Juan Puerto Rico (1979)218\u2013223.","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010303"},{"key":"e_1_2_1_5_2","volume-title":"Inequalities for random walks on trees","author":"Devroye L.","year":"1988"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(86)80005-1"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048274"},{"key":"e_1_2_1_8_2","unstructured":"M. H.Konsowa Random walks on trees. Ph.D. thesis. University of Cincinnati (1988)."},{"key":"e_1_2_1_9_2","volume-title":"Random walks and percolation on trees","author":"Lyons R.","year":"1988"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/S144678870001274X"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90234-4"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190140505","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190140505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T19:06:05Z","timestamp":1698001565000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190140505"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,11]]},"references-count":10,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1990,11]]}},"alternative-id":["10.1002\/jgt.3190140505"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190140505","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,11]]}}}