{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:16:47Z","timestamp":1762273007443},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2022,9,23]],"date-time":"2022-09-23T00:00:00Z","timestamp":1663891200000},"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":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline1.png\" \/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-regular graph on <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline2.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices contains a spanning subgraph in which the number of vertices of each degree between <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline3.png\" \/><jats:tex-math>\n$0$\n<\/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=\"S0963548322000220_inline4.png\" \/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> deviates from <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline5.png\" \/><jats:tex-math>\n$\\frac{n}{d+1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline6.png\" \/><jats:tex-math>\n$2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. The second is that every graph on <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline7.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices with minimum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline8.png\" \/><jats:tex-math>\n$\\delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains a spanning subgraph in which the number of vertices of each degree does not exceed <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline9.png\" \/><jats:tex-math>\n$\\frac{n}{\\delta +1}+2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline10.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In particular we show that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline11.png\" \/><jats:tex-math>\n$d^3 \\log n \\leq o(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> then every <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline12.png\" \/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-regular graph with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline13.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices contains a spanning subgraph in which the number of vertices of each degree between <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline14.png\" \/><jats:tex-math>\n$0$\n<\/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=\"S0963548322000220_inline15.png\" \/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline16.png\" \/><jats:tex-math>\n$(1+o(1))\\frac{n}{d+1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We also prove that any graph with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline17.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices and minimum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline18.png\" \/><jats:tex-math>\n$\\delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains a spanning subgraph in which no degree is repeated more than <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000220_inline19.png\" \/><jats:tex-math>\n$(1+o(1))\\frac{n}{\\delta +1}+2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> times.<\/jats:p>","DOI":"10.1017\/s0963548322000220","type":"journal-article","created":{"date-parts":[[2022,9,23]],"date-time":"2022-09-23T12:12:16Z","timestamp":1663935136000},"page":"269-283","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":5,"title":["Irregular subgraphs"],"prefix":"10.1017","volume":"32","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fan","family":"Wei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,9,23]]},"reference":[{"key":"S0963548322000220_ref17","unstructured":"[17] Schrijver, A. (2003) Combinatorial Optimization, Polyhedra and Efficiency, Vol. A. Paths, Flows, Matchings,Vol. 24 of Algorithms and Combinatorics, Springer, xxxviii+647pp."},{"key":"S0963548322000220_ref11","first-page":"765","volume-title":"Graph Theory, Combinatorics and Applications","author":"Lehel","year":"1991"},{"key":"S0963548322000220_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22772"},{"key":"S0963548322000220_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10056"},{"key":"S0963548322000220_ref6","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1002\/jgt.20313","article-title":"Irregularity strength of dense graphs","volume":"58","author":"Cuckler","year":"2008","journal-title":"J. Graph Theory"},{"key":"S0963548322000220_ref13","doi-asserted-by":"publisher","DOI":"10.37236\/806"},{"key":"S0963548322000220_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90022-6"},{"key":"S0963548322000220_ref12","doi-asserted-by":"publisher","DOI":"10.1137\/120886650"},{"key":"S0963548322000220_ref3","first-page":"xiv","volume-title":"The Probabilistic Method","author":"Alon","year":"2016"},{"key":"S0963548322000220_ref9","unstructured":"[9] Hajnal, A. and Szemer\u00e9di, E. (1970) Proof of a conjecture of Erd\u0151s. In Combinatorial Theory and its Applications, Vol. II(P. Erd\u0151s, A. R\u00e9nyi and V. T. S\u00f3s, eds), Vol. 4 of Colloq. Math. Soc. J. Bolyai, North Holland, pp. 601\u2013623."},{"key":"S0963548322000220_ref2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1002\/1097-0118(200102)36:2<75::AID-JGT3>3.0.CO;2-E","article-title":"Embedding of graphs in two-irregular graphs","volume":"36","author":"Axenovich","year":"2001","journal-title":"J. Graph Theory"},{"key":"S0963548322000220_ref7","unstructured":"[7] Faudree, R. J. and Lehel, J. (1987) Bound on the Irregularity Strength of Regular Graphs, Vol. 52 of Colloq. Math. Soc. Janos Bolyai, North Holland, pp. 247\u2013256."},{"key":"S0963548322000220_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2005.05.035"},{"key":"S0963548322000220_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/090774112"},{"key":"S0963548322000220_ref5","unstructured":"[5] Chartrand, G. , Jacobson, M. S. , Lehel, J. , Oellermann, O. R. , Ruiz, S. and Saba, F. (1986) Irregular networks. In Proceedings of 250th Anniversary Conference on Graph Theory, Fort Wayne, Indiana."},{"key":"S0963548322000220_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/070707385"},{"key":"S0963548322000220_ref16","doi-asserted-by":"crossref","unstructured":"[16] Przyby\u0142o, J. and Wei, F. (2021) On the asymptotic confirmation of the Faudree-Lehel Conjecture for general graphs, arXiv:2109.04317.","DOI":"10.1002\/jgt.22772"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T08:42:29Z","timestamp":1676450549000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000220\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,23]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["S0963548322000220"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000220","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,23]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}