{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:31:44Z","timestamp":1760711504076,"version":"3.43.0"},"reference-count":13,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T00:00:00Z","timestamp":1746316800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>ABSTRACT<\/jats:title><jats:p>Let  be a graph on  vertices, with complement . The spectral gap of the transition probability matrix of a random walk on  is used to estimate how fast the random walk becomes stationary. We prove that the larger spectral gap of  and  is . Moreover, if all degrees are  and , then the larger spectral gap of  and  is . We also show that if the maximum degree is  or if  is a join of two graphs, then the spectral gap of  is . Finally, we provide a family of connected graphs with connected complements such that the larger spectral gap of  and  is .<\/jats:p>","DOI":"10.1002\/jgt.23253","type":"journal-article","created":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T23:01:11Z","timestamp":1746399671000},"page":"132-144","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Nordhaus\u2013Gaddum Problem for the Spectral Gap of a Graph"],"prefix":"10.1002","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0281-7984","authenticated-orcid":false,"given":"Sooyeong","family":"Kim","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics York University Toronto Ontario Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2981-3577","authenticated-orcid":false,"given":"Neal","family":"Madras","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics York University Toronto Ontario Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2025,5,4]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/2306658"},{"key":"e_1_2_9_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.12.018"},{"key":"e_1_2_9_4_1","doi-asserted-by":"publisher","DOI":"10.1198\/016214503388619193"},{"key":"e_1_2_9_5_1","doi-asserted-by":"crossref","unstructured":"F.Chung Spectral Graph Theory CBMS Regional Conference Series in Mathematics vol.92 xii\u2009+\u2009207 (American Mathematical Society 1997).","DOI":"10.1090\/cbms\/092"},{"key":"e_1_2_9_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2018.07.002"},{"key":"e_1_2_9_7_1","unstructured":"D.AldousandJ.Fill Reversible Markov Chains and Random Walks on Graphs(2002) http:\/\/www.stat.berkeley.edu\/~aldous\/RWG\/book.html."},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2024.128920"},{"volume-title":"Markov Chains and Mixing Times","year":"2009","author":"Levin D. A.","key":"e_1_2_9_9_1"},{"key":"e_1_2_9_10_1","unstructured":"S.Kim N.Madras A.Chan M.Kempton S.Kirkland andA.Knudson \u201cBounds on Kemeny's Constant of a Graph and the Nordhaus\u2010Gaddum Problem \u201darXiv preprint arXiv:2309.05171(2023)."},{"key":"e_1_2_9_11_1","unstructured":"J. A.BondyandU. S. R.Murty Graph Theory With Applications x + 264 (American Elsevier Publishing Co. Inc. New York 1976)."},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1985.11971579"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_9_14_1","first-page":"557","article-title":"Bounds on the l2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality","volume":"309","author":"Lawler G. F.","year":"1988","journal-title":"Transactions of the American Mathematical Society"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.23253","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T10:06:04Z","timestamp":1754906764000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.23253"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,4]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["10.1002\/jgt.23253"],"URL":"https:\/\/doi.org\/10.1002\/jgt.23253","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"type":"print","value":"0364-9024"},{"type":"electronic","value":"1097-0118"}],"subject":[],"published":{"date-parts":[[2025,5,4]]},"assertion":[{"value":"2024-06-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}