{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T23:51:25Z","timestamp":1776210685719,"version":"3.50.1"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2020,9,28]],"date-time":"2020-09-28T00:00:00Z","timestamp":1601251200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Bollob\u00e1s and Nikiforov (<jats:italic>J. Combin. Theory Ser. B.<\/jats:italic><jats:bold>97<\/jats:bold> (2007) 859\u2013865) conjectured the following. If <jats:italic>G<\/jats:italic> is a <jats:italic>K<\/jats:italic><jats:sub><jats:italic>r+<\/jats:italic>1<\/jats:sub>-free graph on at least <jats:italic>r+<\/jats:italic>1 vertices and <jats:italic>m<\/jats:italic> edges, then <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000462_inline1.png\"\/><jats:tex-math>${\\rm{\\lambda }}_1^2(G) + {\\rm{\\lambda }}_2^2(G) \\le (r - 1)\/r \\cdot 2m$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>\u03bb<\/jats:italic><jats:sub>1<\/jats:sub> (<jats:italic>G<\/jats:italic>)and <jats:italic>\u03bb<\/jats:italic><jats:sub>2<\/jats:sub> (<jats:italic>G<\/jats:italic>) are the largest and the second largest eigenvalues of the adjacency matrix <jats:italic>A<\/jats:italic>(<jats:italic>G<\/jats:italic>), respectively. In this paper we confirm the conjecture in the case r=2, by using tools from doubly stochastic matrix theory, and also characterize all families of extremal graphs. Motivated by classic theorems due to Erd\u00f6s and Nosal respectively, we prove that every non-bipartite graph of order and size contains a triangle if one of the following is true: (i) <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000462_inline2.png\"\/><jats:tex-math>${{\\rm{\\lambda }}_1}(G) \\ge \\sqrt {m - 1} $<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000462_inline3.png\"\/><jats:tex-math>$G \\ne {C_5} \\cup (n - 5){K_1}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and (ii) <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000462_inline4.png\"\/><jats:tex-math>${{\\rm{\\lambda }}_1}(G) \\ge {{\\rm{\\lambda }}_1}(S({K_{[(n - 1)\/2],[(n - 1)\/2]}}))$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000462_inline5.png\"\/><jats:tex-math>$G \\ne S({K_{[(n - 1)\/2],[(n - 1)\/2]}})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000462_inline6.png\"\/><jats:tex-math>$S({K_{[(n - 1)\/2],[(n - 1)\/2]}})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is obtained from <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000462_inline7.png\"\/><jats:tex-math>${K_{[(n - 1)\/2],[(n - 1)\/2]}}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by subdividing an edge. Both conditions are best possible. We conclude this paper with some open problems.<\/jats:p>","DOI":"10.1017\/s0963548320000462","type":"journal-article","created":{"date-parts":[[2020,9,28]],"date-time":"2020-09-28T07:41:56Z","timestamp":1601278916000},"page":"258-270","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":80,"title":["Eigenvalues and triangles in graphs"],"prefix":"10.1017","volume":"30","author":[{"given":"Huiqiu","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Ning","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baoyindureng","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,9,28]]},"reference":[{"key":"S0963548320000462_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2016.01.021"},{"key":"S0963548320000462_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.008"},{"key":"S0963548320000462_ref21","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1997"},{"key":"S0963548320000462_ref33","unstructured":"[33] Nosal, E. (1970) Eigenvalues of graphs. Master\u2019s thesis, University of Calgary."},{"key":"S0963548320000462_ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.04.006"},{"key":"S0963548320000462_ref34","doi-asserted-by":"publisher","DOI":"10.26493\/1855-3974.749.264"},{"key":"S0963548320000462_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(85)90092-8"},{"key":"S0963548320000462_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90069-9"},{"key":"S0963548320000462_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.12.002"},{"key":"S0963548320000462_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2009.01.002"},{"key":"S0963548320000462_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261315"},{"key":"S0963548320000462_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.07.007"},{"key":"S0963548320000462_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.01.003"},{"key":"S0963548320000462_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2019.02.016"},{"key":"S0963548320000462_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90133-2"},{"key":"S0963548320000462_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2015.08.007"},{"key":"S0963548320000462_ref27","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-053-6"},{"key":"S0963548320000462_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00254-O"},{"key":"S0963548320000462_ref13","volume-title":"Spectra of Graphs: Theory and Application","author":"Cvetkovi\u0107","year":"1980"},{"key":"S0963548320000462_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2004.08.014"},{"key":"S0963548320000462_ref32","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139004114.005"},{"key":"S0963548320000462_ref23","doi-asserted-by":"publisher","DOI":"10.1080\/03081087.2016.1151854"},{"key":"S0963548320000462_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90007-G"},{"key":"S0963548320000462_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.02.003"},{"key":"S0963548320000462_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.02.008"},{"key":"S0963548320000462_ref10","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1989-0965008-X"},{"key":"S0963548320000462_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02006065"},{"key":"S0963548320000462_ref18","unstructured":"[18] Hoffman, A. J. and Smith, J. H. (1975) On the spectral radii of topologically equivalent graphs. In Recent Advances in Graph Theory ( Fiedler, M. , ed.), pp. 273\u2013281. Academia Praha."},{"key":"S0963548320000462_ref38","unstructured":"[38] Zhai, M. Q. , Lin, H. Q. and Shu, J. In preparation."},{"key":"S0963548320000462_ref39","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/147"},{"key":"S0963548320000462_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20581"},{"key":"S0963548320000462_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"S0963548320000462_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004928"},{"key":"S0963548320000462_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00605-017-1055-9"},{"key":"S0963548320000462_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70492-8"},{"key":"S0963548320000462_ref22","volume-title":"Changyong Budengshi [Applied Inequalities]","author":"Kuang","year":"2003"},{"key":"S0963548320000462_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5"},{"key":"S0963548320000462_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90172-8"},{"key":"S0963548320000462_ref40","doi-asserted-by":"publisher","DOI":"10.1007\/s10587-005-0064-3"},{"key":"S0963548320000462_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90015-X"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000462","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T12:51:03Z","timestamp":1614862263000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000462\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,28]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["S0963548320000462"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000462","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,28]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}