{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T13:10:10Z","timestamp":1748437810326,"version":"3.37.3"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T00:00:00Z","timestamp":1649289600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T00:00:00Z","timestamp":1649289600000},"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":["J Math Imaging Vis"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A nonnegative integer sequence is <jats:italic>k<\/jats:italic>-graphic if it is the degree sequence of a <jats:italic>k<\/jats:italic>-uniform simple hypergraph. The problem of deciding whether a given sequence <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\pi $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c0<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is 3-graphic has recently been proved to be NP-complete, after years of studies. Thus, it acquires primary relevance to detect classes of degree sequences whose graphicality can be tested in polynomial time in order to restrict the NP-hard core of the problem and design algorithms that can also be useful in different research areas. Several necessary and few sufficient conditions for <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\pi $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c0<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to be <jats:italic>k<\/jats:italic>-graphic, with <jats:inline-formula><jats:alternatives><jats:tex-math>$$k\\ge 3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, appear in the literature. Frosini et al. defined a polynomial time algorithm to reconstruct <jats:italic>k<\/jats:italic>-uniform hypergraphs having regular or almost regular degree sequences. Our study fits in this research line providing a combinatorial characterization of span-two sequences, i.e., sequences of the form <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\pi =(d,\\ldots ,d,d-1,\\ldots ,d-1,d-2,\\ldots ,d-2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c0<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u2026<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u2026<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u2026<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:tex-math>$$d\\ge 2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which are degree sequences of some 3-uniform hypergraphs. Then, we define a polynomial time algorithm to reconstruct one of the related 3-uniform hypergraphs. Our results are likely to be easily generalized to <jats:inline-formula><jats:alternatives><jats:tex-math>$$k \\ge 4$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>4<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and to other families of degree sequences having simple characterization, such as gap-free sequences.<\/jats:p>","DOI":"10.1007\/s10851-022-01074-2","type":"journal-article","created":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T09:18:00Z","timestamp":1649323080000},"page":"693-704","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Reconstruction of 3-Uniform Hypergraphs from Degree Sequences of Span-Two"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1330-4735","authenticated-orcid":false,"given":"Giulia","family":"Palma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Frosini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simone","family":"Rinaldi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,7]]},"reference":[{"key":"1074_CR1","volume-title":"Hyperpgraphs","author":"C Berge","year":"1989","unstructured":"Berge, C.: Hyperpgraphs. North-Holland, Amsterdam (1989)"},{"key":"1074_CR2","doi-asserted-by":"publisher","first-page":"P14","DOI":"10.37236\/3414","volume":"20","author":"S Behrens","year":"2013","unstructured":"Behrens, S., Erbes, C., Ferrara, M., Hartke, S.G., Reiniger, B., Spinoza, H.: New results on degree sequences of uniform hypergraphs. Electron. J. Comb. 20, P14 (2013)","journal-title":"Electron. J. Comb."},{"key":"1074_CR3","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-319-32360-2_7","volume-title":"Discrete Geometry for Computer Imagery. DGCI 2016","author":"S Brlek","year":"2016","unstructured":"Brlek, S., Frosini, A.: A tomographical interpretation of a sufficient condition on h-graphical sequences. In: Normand, N., Gu\u00e9don, J., Autrusseau, F. (eds.) Discrete Geometry for Computer Imagery. DGCI 2016, pp. 95\u2013104. Springer, Cham (2016)"},{"key":"1074_CR4","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0166-218X(86)90028-4","volume":"14","author":"CJ Colbourn","year":"1986","unstructured":"Colbourn, C.J., Kocay, W.L., Stinson, D.R.: Some NP-complete problems for hypergraph degree sequences. Discrete Appl. Math. 14, 239\u2013254 (1986)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1074_CR5","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1090\/S0002-9939-1975-0384610-1","volume":"53","author":"AK Dewdney","year":"1975","unstructured":"Dewdney, A.K.: Degree sequences in complexes and hypergraphs. Proc. Am. Math. Soc. 53(2), 535\u2013540 (1975)","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"1074_CR6","doi-asserted-by":"publisher","first-page":"2067","DOI":"10.1137\/17M1134482","volume":"32","author":"A Deza","year":"2018","unstructured":"Deza, A., Levin, A., Meesum, S.M., Onn, S.: Optimization over degree sequences. SIAM J. Discrete Math. 32(3), 2067\u20132079 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"1074_CR7","first-page":"264","volume":"11","author":"P Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s, P., Gallai, T.: Graphs with prescribed degrees of vertices (Hungarian). Mat. Lapok 11, 264\u2013274 (1960)","journal-title":"Mat. Lapok"},{"key":"1074_CR8","first-page":"338","volume-title":"Discrete Geometry and Mathematical Morphology. DGMM 2021. Lecture Notes in Computer Science","author":"A Frosini","year":"2021","unstructured":"Frosini, A., Palma, G., Rinaldi, S.: On the reconstruction of 3-uniform hypergraphs from step-two degree sequences. In: Lindblad, J., Malmberg, F., Sladoje, N. (eds.) Discrete Geometry and Mathematical Morphology. DGMM 2021. Lecture Notes in Computer Science, vol. 12708, pp. 338\u2013347. Springer, Cham (2021)"},{"key":"1074_CR9","first-page":"300","volume-title":"Discrete Geometry for Computer Imagery. DGCI 2013. Lecture Notes in Computer Science","author":"A Frosini","year":"2013","unstructured":"Frosini, A., Picouleau, C., Rinaldi, S.: On the degree sequences of uniform hypergraphs. In: Gonzalez-Diaz, R., Jimenez, M.J., Medrano, B. (eds.) Discrete Geometry for Computer Imagery. DGCI 2013. Lecture Notes in Computer Science, vol. 7749, pp. 300\u2013310. Springer, Berlin (2013)"},{"issue":"4","key":"1074_CR10","first-page":"657","volume":"5","author":"EN Gilbert","year":"1961","unstructured":"Gilbert, E.N., Riordan, J.: Symmetry types of periodic sequences. Ill. J. Math. 5(4), 657\u2013665 (1961)","journal-title":"Ill. J. Math."},{"key":"1074_CR11","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1137\/S0097539798344112","volume":"29","author":"F Ruskey","year":"1999","unstructured":"Ruskey, F., Sawada, J.: An efficient algorithm for generating necklaces with fixed density. SIAM J. Comput. 29, 671\u2013684 (1999)","journal-title":"SIAM J. Comput."},{"key":"1074_CR12","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1016\/S0304-3975(03)00049-5","volume":"301","author":"J Sawada","year":"2003","unstructured":"Sawada, J.: A fast algorithm to generate necklaces with fixed content. Theor. Comput. Sci. 301, 477\u2013489 (2003)","journal-title":"Theor. Comput. Sci."}],"container-title":["Journal of Mathematical Imaging and Vision"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-022-01074-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10851-022-01074-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-022-01074-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T13:19:36Z","timestamp":1662038376000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10851-022-01074-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,7]]},"references-count":12,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1074"],"URL":"https:\/\/doi.org\/10.1007\/s10851-022-01074-2","relation":{},"ISSN":["0924-9907","1573-7683"],"issn-type":[{"type":"print","value":"0924-9907"},{"type":"electronic","value":"1573-7683"}],"subject":[],"published":{"date-parts":[[2022,4,7]]},"assertion":[{"value":"7 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Open access funding note has been updated","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}