{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T04:26:41Z","timestamp":1765772801074},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T00:00:00Z","timestamp":1570492800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The famous Erd\u0151s\u2013Gallai theorem on the Tur\u00e1n number of paths states that every graph with <jats:italic>n<\/jats:italic> vertices and <jats:italic>m<\/jats:italic> edges contains a path with at least (2<jats:italic>m<\/jats:italic>)\/<jats:italic>n<\/jats:italic> edges. In this note, we first establish a simple but novel extension of the Erd\u0151s\u2013Gallai theorem by proving that every graph <jats:italic>G<\/jats:italic> contains a path with at least \n<jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548319000269_eqnU1\" \/><jats:tex-math>$${{(s + 1){N_{s + 1}}(G)} \\over {{N_s}(G)}} + s - 1$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula>\nedges, where <jats:italic>N<\/jats:italic><jats:sub><jats:italic>j<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) denotes the number of <jats:italic>j<\/jats:italic>-cliques in <jats:italic>G<\/jats:italic> for 1<jats:italic>\u2264 j \u2264 \u03c9(G)<\/jats:italic>. We also construct a family of graphs which shows our extension improves the estimate given by the Erd\u0151s\u2013Gallai theorem. Among applications, we show, for example, that the main results of [20], which are on the maximum possible number of <jats:italic>s<\/jats:italic>-cliques in an <jats:italic>n<\/jats:italic>-vertex graph without a path with \u2113 vertices (and without cycles of length at least <jats:italic>c<\/jats:italic>), can be easily deduced from this extension. Indeed, to prove these results, Luo [20] generalized a classical theorem of Kopylov and established a tight upper bound on the number of <jats:italic>s<\/jats:italic>-cliques in an <jats:italic>n<\/jats:italic>-vertex 2-connected graph with circumference less than <jats:italic>c<\/jats:italic>. We prove a similar result for an <jats:italic>n<\/jats:italic>-vertex 2-connected graph with circumference less than <jats:italic>c<\/jats:italic> and large minimum degree. We conclude this paper with an application of our results to a problem from spectral extremal graph theory on consecutive lengths of cycles in graphs.<\/jats:p>","DOI":"10.1017\/s0963548319000269","type":"journal-article","created":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T07:41:29Z","timestamp":1570520489000},"page":"128-136","source":"Crossref","is-referenced-by-count":27,"title":["Extensions of the Erd\u0151s\u2013Gallai theorem and Luo\u2019s theorem"],"prefix":"10.1017","volume":"29","author":[{"given":"Bo","family":"Ning","sequence":"first","affiliation":[]},{"given":"Xing","family":"Peng","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,10,8]]},"reference":[{"key":"S0963548319000269_ref22","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-24.4.739"},{"key":"S0963548319000269_ref8","first-page":"459","article-title":"On the number of complete subgraphs contained in certain graphs","volume":"7","author":"Erd\u0151s","year":"1962","journal-title":"Magya Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"S0963548319000269_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.016"},{"key":"S0963548319000269_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.03.004"},{"key":"S0963548319000269_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2018.06.006"},{"key":"S0963548319000269_ref18","first-page":"593","article-title":"Maximal paths and cycles in a graph.","volume":"18","author":"Kopylov","year":"1977","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"S0963548319000269_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2007.09.029"},{"key":"S0963548319000269_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22390"},{"key":"S0963548319000269_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90045-3"},{"key":"S0963548319000269_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.08.005"},{"key":"S0963548319000269_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90024-T"},{"key":"S0963548319000269_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205072"},{"key":"S0963548319000269_ref7","first-page":"227","article-title":"Remarks on a paper of P\u00f3sa","volume":"7","author":"Erd\u0151s","year":"1962","journal-title":"Magya Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"S0963548319000269_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90080-5"},{"key":"S0963548319000269_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(71)90019-7"},{"key":"S0963548319000269_ref2","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s","year":"1978"},{"key":"S0963548319000269_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90423-Y"},{"key":"S0963548319000269_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02024498"},{"key":"S0963548319000269_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39286-3_7"},{"key":"S0963548319000269_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.04.001"},{"key":"S0963548319000269_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.12.008"},{"key":"S0963548319000269_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01902497"},{"key":"S0963548319000269_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.003"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000269","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,14]],"date-time":"2020-01-14T10:57:10Z","timestamp":1578999430000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000269\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,8]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["S0963548319000269"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000269","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,8]]}}}