{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:49:23Z","timestamp":1780822163753,"version":"3.54.1"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2013,4,5]],"date-time":"2013-04-05T00:00:00Z","timestamp":1365120000000},"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":[[2013,5]]},"abstract":"<jats:p>One of the first graph-theoretical problems to be given serious attention (in the 1950s) was the decision whether a given integer sequence is equal to the degree sequence of a simple graph (or<jats:italic>graphical<\/jats:italic>, for short). One method to solve this problem is the greedy algorithm of Havel and Hakimi, which is based on the<jats:italic>swap<\/jats:italic>operation. Another, closely related question is to find a sequence of swap operations to transform one graphical realization into another of the same degree sequence. This latter problem has received particular attention in the context of rapidly mixing Markov chain approaches to uniform sampling of all possible realizations of a given degree sequence. (This becomes a matter of interest in the context of the study of large social networks, for example.) Previously there were only crude upper bounds on the shortest possible length of such swap sequences between two realizations. In this paper we develop formulae (Gallai-type identities) for the<jats:italic>swap-distance<\/jats:italic>s of any two realizations of simple undirected or directed degree sequences. These identities considerably improve the known upper bounds on the swap-distances.<\/jats:p>","DOI":"10.1017\/s0963548313000096","type":"journal-article","created":{"date-parts":[[2013,4,5]],"date-time":"2013-04-05T10:50:44Z","timestamp":1365159044000},"page":"366-383","source":"Crossref","is-referenced-by-count":19,"title":["On the Swap-Distances of Different Realizations of a Graphical Degree Sequence"],"prefix":"10.1017","volume":"22","author":[{"given":"P\u00c9TER L.","family":"ERD\u0150S","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ZOLT\u00c1N","family":"KIR\u00c1LY","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ISTV\u00c1N","family":"MIKL\u00d3S","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2013,4,5]]},"reference":[{"key":"S0963548313000096_ref20","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-033-3"},{"key":"S0963548313000096_ref19","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1952-028-2"},{"key":"S0963548313000096_ref18","doi-asserted-by":"publisher","DOI":"10.2307\/2372318"},{"key":"S0963548313000096_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90068-X"},{"key":"S0963548313000096_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90037-X"},{"key":"S0963548313000096_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/0110037"},{"key":"S0963548313000096_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(65)90340-6"},{"key":"S0963548313000096_ref4","doi-asserted-by":"crossref","first-page":"#R66","DOI":"10.37236\/338","article-title":"A simple Havel\u2013Hakimi type algorithm to realize graphical degree sequences of directed graphs","volume":"17","author":"Erd\u0151s","year":"2010","journal-title":"Electron. J. Combin."},{"key":"S0963548313000096_ref12","unstructured":"Kir\u00e1ly Z. (2012) Recognizing graphic degree sequences and generating all realizations. EGRES Technical Report TR-2011-11. http:\/\/www.cs.elte.hu\/egres"},{"key":"S0963548313000096_ref3","first-page":"264","article-title":"Graphs with prescribed degree of vertices (in Hungarian).","volume":"11","author":"Erd\u0151s","year":"1960","journal-title":"Mat. Lapok"},{"key":"S0963548313000096_ref15","doi-asserted-by":"crossref","unstructured":"LaMar M. D. (2011) Directed 3-cycle anchored digraphs and their application in the uniform sampling of realizations from a fixed degree sequence. In ACM & IEEE & SCS Proc. 2011 Winter Simulation Conference ( S. Jain , R. R. Creasey et al., eds), pp. 1\u201312.","DOI":"10.1109\/WSC.2011.6148031"},{"key":"S0963548313000096_ref6","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1957.7.1073"},{"key":"S0963548313000096_ref5","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.831"},{"key":"S0963548313000096_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89550-3_3"},{"key":"S0963548313000096_ref21","volume-title":"Introduction to Graph Theory","author":"West","year":"2001"},{"key":"S0963548313000096_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16926-7_21"},{"key":"S0963548313000096_ref11","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/42\/39\/392001"},{"key":"S0963548313000096_ref10","doi-asserted-by":"crossref","first-page":"477","DOI":"10.21136\/CPM.1955.108220","article-title":"A remark on the existence of finite graphs (in Czech)","volume":"80","author":"Havel","year":"1955","journal-title":"\u010casopis P\u011bst. Mat."},{"key":"S0963548313000096_ref17","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1957-044-3"},{"key":"S0963548313000096_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392606"},{"key":"S0963548313000096_ref7","doi-asserted-by":"crossref","first-page":"#P234","DOI":"10.37236\/721","article-title":"A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs","volume":"18","author":"Greenhill","year":"2011","journal-title":"Electron. J. Combin."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000096","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,13]],"date-time":"2022-02-13T04:00:06Z","timestamp":1644724806000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000096\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,5]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["S0963548313000096"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000096","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,5]]}}}