{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T15:59:26Z","timestamp":1792857566893,"version":"4.5.0"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["522728"],"award-info":[{"award-number":["522728"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>The toughness $t(G)$ of a connected graph $G$ is defined as $t(G)=\\min\\{\\frac{|S|}{c(G-S)}\\}$, in which the minimum is taken over all proper subsets $S\\subset V(G)$ such that $c(G-S)&gt;1$, where $c(G-S)$ denotes the number of components of $G-S$. Let $\\lambda$ denote the second largest absolute eigenvalue of the adjacency matrix of a graph. For any connected $d$-regular graph $G$, it has been shown by Alon that $t(G)&gt;\\frac{1}{3}(\\frac{d^2}{d\\lambda+\\lambda^2}-1)$, through which he was able to show that for every $t$ and $g$ there are $t$-tough graphs of girth strictly greater than $g$ and thus disproved in a strong sense a conjecture of Chv\u00e1tal on pancyclicity. Brouwer independently discovered a better bound $t(G)&gt;\\frac{d}{\\lambda}-2$ for any connected $d$-regular graph $G$, while he also conjectured that the lower bound can be improved to $t(G)\\ge \\frac{d}{\\lambda} - 1$. We confirm this conjecture.<\/jats:p>","DOI":"10.1137\/20m1372652","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T11:29:18Z","timestamp":1620646158000},"page":"948-952","source":"Crossref","is-referenced-by-count":26,"title":["A Proof of Brouwer's Toughness Conjecture"],"prefix":"10.1137","volume":"35","author":[{"given":"Xiaofeng","family":"Gu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022453926717"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"atypb3","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , Wiley, New York, 2016."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1051"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00154-J"},{"key":"atypb6","first-page":"37","volume":"9","author":"Brouwer A. E.","year":"1996","journal-title":"CWI Quarterly"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2004.08.014"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90138-6"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s10587-016-0300-z"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.12.004"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103255"},{"key":"atypb12","unstructured":"W. H. Haemers,\n                      Eigenvalue Techniques in Design and Graph Theory\n                      , Ph.D. thesis, 1979."},{"key":"atypb13","first-page":"199","author":"Krivelevich M.","year":"2006","journal-title":"Berlin"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"D. Park, A. Ostuni, N. Hayes, A. Banerjee, T. Wakhare, W. Wong, and S. Cioab\u0103,\n                      The Toughness of Kneser Graphs\n                      , preprint,https:\/\/arxiv.org\/abs\/2008.08183, 2020.","DOI":"10.1016\/j.disc.2021.112484"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"A. Thomason,\n                      Pseudo-random graphs\n                      , in Proceedings of Random Graphs (Pozna\u0144, 1985), Ann. Discrete Math. 33, M. Karo\u0144ski, ed., Elsevier, Amsterdam, 1987, pp. 307-331.","DOI":"10.1016\/S0304-0208(08)73063-9"},{"key":"atypb16","first-page":"173","author":"Thomason A.","year":"1987","journal-title":"UK"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1372652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:44:10Z","timestamp":1787319850000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1372652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1372652"],"URL":"https:\/\/doi.org\/10.1137\/20m1372652","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}