{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:58:03Z","timestamp":1781305083976,"version":"3.54.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_5","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:33:39Z","timestamp":1781303619000},"page":"64-80","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Degree Realization with\u00a0Minimum Dominating Set"],"prefix":"10.1007","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Igor","family":"Kalinichev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0012-365X(94)00104-Q","volume":"136","author":"M Aigner","year":"1994","unstructured":"Aigner, M., Triesch, E.: Realizability and uniqueness in graphs. Discr. Math. 136, 3\u201320 (1994)","journal-title":"Discr. Math."},{"issue":"1","key":"5_CR2","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/0196-6774(85)90022-7","volume":"6","author":"RP Anstee","year":"1985","unstructured":"Anstee, R.P.: An algorithmic proof of Tutte\u2019s $$f$$-factor theorem. J. Alg. 6(1), 112\u2013131 (1985)","journal-title":"J. Alg."},{"issue":"1\u20132","key":"5_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(90)90126-W","volume":"27","author":"RP Anstee","year":"1990","unstructured":"Anstee, R.P.: Simplified existence theorems for $$(g, f)$$-factors. Discr. Appl. Math. 27(1\u20132), 29\u201338 (1990)","journal-title":"Discr. Appl. Math."},{"issue":"6","key":"5_CR4","doi-asserted-by":"publisher","first-page":"1687","DOI":"10.1016\/j.disc.2019.02.005","volume":"342","author":"F Bock","year":"2019","unstructured":"Bock, F., Rautenbach, D.: On matching numbers of tree and bipartite degree sequences. Discr. Math. 342(6), 1687\u20131695 (2019)","journal-title":"Discr. Math."},{"issue":"1","key":"5_CR5","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1017\/S0004972700002872","volume":"33","author":"SA Choudum","year":"1991","unstructured":"Choudum, S.A.: A simple proof of the Erd\u00f6s-Gallai theorem on graph sequences. Bull. Austral. Math. Soc. 33(1), 67\u201370 (1991)","journal-title":"Bull. Austral. Math. Soc."},{"issue":"2","key":"5_CR6","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0095-8956(78)90016-3","volume":"24","author":"V Chungphaisan","year":"1978","unstructured":"Chungphaisan, V.: Construction of hamiltonian graphs and bigraphs with prescribed degrees. J. Comb. Theory B 24(2), 154\u2013163 (1978)","journal-title":"J. Comb. Theory B"},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.disc.2005.09.005","volume":"304","author":"G Dahl","year":"2005","unstructured":"Dahl, G., Flatberg, T.: A remark concerning graphical sequences. Discr. Math. 304, 62\u201364 (2005)","journal-title":"Discr. Math."},{"key":"5_CR8","first-page":"264","volume":"11","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Gallai, T.: Graphs with prescribed degrees of vertices [hungarian]. Mat. Lapok (N.S.) 11, 264\u2013274 (1960)","journal-title":"Mat. Lapok (N.S.)"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P.L., Kharel, S.R., Mezei, T.R., Toroczkai, Z.: New results on graph matching from degree-preserving growth. Mathematics 12(22) (2024)","DOI":"10.3390\/math12223518"},{"issue":"4","key":"5_CR10","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"166","DOI":"10.4153\/CJM-1965-016-2","volume":"17","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Hoffman, A.J., McAndrew, M.H.: Some properties of graphs with multiple edges. Can. J. Math. 17, 166\u2013177 (1965)","journal-title":"Can. J. Math."},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.dam.2016.01.040","volume":"206","author":"M Gentner","year":"2016","unstructured":"Gentner, M., Henning, M.A., Rautenbach, D.: Largest domination number and smallest independence number of forests with given degree sequence. Discr. Appl. Math. 206, 181\u2013187 (2016)","journal-title":"Discr. Appl. Math."},{"issue":"1","key":"5_CR13","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1002\/jgt.22189","volume":"88","author":"M Gentner","year":"2018","unstructured":"Gentner, M., Henning, M.A., Rautenbach, D.: Smallest domination number and largest independence number of graphs and forests with given degree sequence. J. Graph Theory 88(1), 131\u2013145 (2018)","journal-title":"J. Graph Theory"},{"key":"5_CR14","unstructured":"Gould, R.J., Jackson, M.S., Lehel, J.: Potentially $$g$$-graphical degree sequences. In: Combinatorics, Graph Theory, and Algorithms, vol.\u00a01, pp. 451\u2013460 (1999)"},{"issue":"3","key":"5_CR15","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/0110037","volume":"10","author":"SL Hakimi","year":"1962","unstructured":"Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph - I. SIAM J. Appl. Math. 10(3), 496\u2013506 (1962)","journal-title":"SIAM J. Appl. Math."},{"key":"5_CR16","first-page":"477","volume":"80","author":"V Havel","year":"1955","unstructured":"Havel, V.: A remark on the existence of finite graphs. Casopis Pest. Mat. 80, 477\u2013480 (1955)","journal-title":"Casopis Pest. Mat."},{"key":"5_CR17","unstructured":"K\u00e9zdy, A., Lehel, J.: Degree sequences of graphs with prescribed clique size. In: Graph Theory, Combinatorics, Algorithms, and Applications, pp. 535\u2013544 (1998)"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0012-365X(73)90037-X","volume":"6","author":"DJ Kleitman","year":"1973","unstructured":"Kleitman, D.J., Wang, D.L.: Algorithms for constructing graphs and digraphs with given valences and factors. Discr. Math. 6, 79\u201388 (1973)","journal-title":"Discr. Math."},{"issue":"4","key":"5_CR19","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0012-365X(73)90068-X","volume":"6","author":"S Kundu","year":"1973","unstructured":"Kundu, S.: The $$k$$-factor conjecture is true. Discr. Math. 6(4), 367\u2013376 (1973)","journal-title":"Discr. Math."},{"issue":"1","key":"5_CR20","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(74)90108-3","volume":"8","author":"S Kundu","year":"1974","unstructured":"Kundu, S.: A factorization theorem for a certain class of graphs. Discr. Math. 8(1), 41\u201347 (1974)","journal-title":"Discr. Math."},{"issue":"2","key":"5_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0012-365X(74)90147-2","volume":"9","author":"S Kundu","year":"1974","unstructured":"Kundu, S.: Generalizations of the $$k$$-factor theorem. Discr. Math. 9(2), 173\u2013179 (1974)","journal-title":"Discr. Math."},{"key":"5_CR22","unstructured":"Rao, A.R.: The clique number of a graph with a given degree sequence. In: ISI Lecture Notes, vol.\u00a04, pp. 251\u2013267 (1979)"},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0095-8956(72)90055-X","volume":"13","author":"AR Rao","year":"1972","unstructured":"Rao, A.R., Rao, S.B.: On factorable degree sequences. J. Comb. Theory B 13, 185\u2013191 (1972)","journal-title":"J. Comb. Theory B"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Rao, S.B.: Towards a theory of forcibly hereditary P-graphic sequences. In: Combinatorics and Graph Theory, pp. 441\u2013458. Springer (1981)","DOI":"10.1007\/BFb0092289"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: 29th ACM STOC, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"3513","DOI":"10.1016\/j.dam.2008.03.033","volume":"156","author":"A Tripathi","year":"2008","unstructured":"Tripathi, A., Tyagi, H.: A simple criterion on degree sequences of graphs. Discr. Appl. Math. 156, 3513\u20133517 (2008)","journal-title":"Discr. Appl. Math."},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1016\/j.disc.2009.09.023","volume":"310","author":"A Tripathi","year":"2010","unstructured":"Tripathi, A., Venugopalan, S., West, D.B.: A short constructive proof of the Erd\u00f6s-Gallai characterization of graphic lists. Discr. Math. 310, 843\u2013844 (2010)","journal-title":"Discr. Math."},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/S0012-365X(02)00886-5","volume":"265","author":"A Tripathi","year":"2003","unstructured":"Tripathi, A., Vijay, S.: A note on a theorem of Erd\u00f6s & Gallai. Discr. Math. 265, 417\u2013420 (2003)","journal-title":"Discr. Math."},{"issue":"21","key":"5_CR29","doi-asserted-by":"publisher","first-page":"2485","DOI":"10.1016\/j.disc.2011.07.024","volume":"311","author":"JH Yin","year":"2011","unstructured":"Yin, J.H.: A rao-type characterization for a sequence to have a realization containing a split graph. Discr. Math. 311(21), 2485\u20132489 (2011)","journal-title":"Discr. Math."},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Yin, J.H.: A short constructive proof of A. R. Rao\u2019s characterization of potentially $$K_{r+1}$$-graphic sequences. Discr. Appl. Math. 160(3), 352\u2013354 (2012)","DOI":"10.1016\/j.dam.2011.10.015"},{"issue":"1","key":"5_CR31","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:33:43Z","timestamp":1781303623000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}