{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T07:05:44Z","timestamp":1770966344856,"version":"3.50.1"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T00:00:00Z","timestamp":1766275200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T00:00:00Z","timestamp":1766275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In this paper we show that prime sum graphs on\n                    <jats:italic>n<\/jats:italic>\n                    vertices \u2013 which are graphs on vertex set\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\{1,2, \\dots ,n\\}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>{<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mo>\u22ef<\/mml:mo>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>}<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    where\n                    <jats:italic>ij<\/jats:italic>\n                    is an edge when\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$i+j$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>i<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>j<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is prime \u2013 contain all trees with at most\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\exp ( c \\log n \/ \\log \\log n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>exp<\/mml:mo>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>c<\/mml:mi>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>\/<\/mml:mo>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    vertices as induced subgraphs. We also prove some results for related graphs, and end with some unsolved problems.\n                  <\/jats:p>","DOI":"10.1007\/s00373-025-02999-2","type":"journal-article","created":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T11:11:43Z","timestamp":1766315503000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Prime Sum Graphs and the Induced Trees They Contain"],"prefix":"10.1007","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-4779-5368","authenticated-orcid":false,"given":"Ernie","family":"Croot","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Jin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,21]]},"reference":[{"issue":"4","key":"2999_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3088513","volume":"64","author":"S Alstrup","year":"2017","unstructured":"Alstrup, S., Dahlgaard, S., Knudsen, M.B.T.: Optimal induced universal graphs and adjacency labeling for trees. J. ACM 64(4), 1\u201322 (2017)","journal-title":"J. ACM"},{"key":"2999_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s00373-020-02241-1","volume":"37","author":"H Chen","year":"2021","unstructured":"Chen, H., Hung-Lin, F., Guo, J.-Y.: Hamiltonicity in prime sum graphs. Graphs Combin. 37, 209\u2013219 (2021)","journal-title":"Graphs Combin."},{"key":"2999_CR3","first-page":"149","volume-title":"Planar Graphs: Theory and Algorithms, chap. 9. Planar Separator Theorem","author":"T Nishizuzeki","year":"2008","unstructured":"Nishizuzeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms, chap. 9. Planar Separator Theorem, pp. 149\u2013170. Dover Books on Mathematics, Courier Dover Publications (2008)"},{"key":"2999_CR4","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Renyi, A.: On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato\u00cdnt. K\u0151zl 5, 17\u201361 (1960)","journal-title":"Magyar Tud. Akad. Mat. Kutato\u00cdnt. K\u0151zl"},{"key":"2999_CR5","doi-asserted-by":"publisher","first-page":"67","DOI":"10.4064\/aa-11-1-67-96","volume":"11","author":"E Fogels","year":"1965","unstructured":"Fogels, E.: On the zeros of $$L$$-functions. Acta Arith 11, 67\u201396 (1965)","journal-title":"Acta Arith"},{"key":"2999_CR6","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jnth.1999.2479","volume":"81","author":"K Ford","year":"2000","unstructured":"Ford, K., Halberstam, H.: The brun-hooley sieve. J. Number Theory 81, 335\u2013350 (2000)","journal-title":"J. Number Theory"},{"key":"2999_CR7","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.2307\/121035","volume":"148","author":"J Friedlander","year":"1998","unstructured":"Friedlander, J., Iwaniec, H.: Asymptotic sieve for primes. Ann. of Math. 148, 1041\u20131065 (1998)","journal-title":"Ann. of Math."},{"key":"2999_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0095-8956(87)90039-6","volume":"42","author":"A Frieze","year":"1987","unstructured":"Frieze, A., Jackson, B.: Large induced trees in sparse random graphs. Jour. of Comb. Theory Ser. B 42, 181\u2013195 (1987)","journal-title":"Jour. of Comb. Theory Ser. B"},{"key":"2999_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02403921","volume":"44","author":"GH Hardy","year":"1923","unstructured":"Hardy, G.H., Littlewood, J.E.: Some problems of \u2018partitio numerorum\u2019: III: on the expression of a number as a sum of primes. Acta Math. 44, 1\u201370 (1923)","journal-title":"Acta Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02999-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02999-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02999-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:05:20Z","timestamp":1770962720000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02999-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,21]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["2999"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02999-2","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,21]]},"assertion":[{"value":"15 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"There is no competing interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"11"}}