{"entities":{"Q1300907":{"pageid":1311657,"ns":120,"title":"Item:Q1300907","lastrevid":46698015,"modified":"2025-12-25T10:26:16Z","type":"item","id":"Q1300907","labels":{"en":{"language":"en","value":"The realization graph of a degree sequence with majorization gap 1 is Hamiltonian"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1331375"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$A61390DC-2869-44D0-A8B1-48D9E063E29A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6d6982b028709b83dd48c57c08ad851b67111eee","datavalue":{"value":{"text":"The realization graph of a degree sequence with majorization gap 1 is Hamiltonian","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1300907$0CA50A57-ECBC-40EC-8BD0-78CAF8075F8A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"19518774766189ddb58172ce9bb0e9117857e051","datavalue":{"value":"0932.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300907$0ADF1378-1C9C-46B2-8A82-878E4F905DD0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3f0db97c822ae33685eaa40a9adaf516fb326d97","datavalue":{"value":"10.1016/S0024-3795(98)10229-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300907$743E0B44-D2DC-4566-8EBA-41FCA7474504","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6176b5644d403b2413c99fd6eb40e53520884999","datavalue":{"value":{"entity-type":"item","numeric-id":686256,"id":"Q686256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$E0101C10-C5D9-4A41-A93F-F987BAF40EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9b3fb3ff79ebe0e00ad86f0808334d1b6856038","datavalue":{"value":{"entity-type":"item","numeric-id":584288,"id":"Q584288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$B302B994-0DCF-44F6-8510-280F3195A4E8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$1E252377-BCEA-452C-ACDA-A86D0C38F32E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b22f0234058b897ad308815846be004cdc7f94b2","datavalue":{"value":{"time":"+2000-03-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1300907$323305A8-B43C-4676-87DF-2833F11DCCF2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dc076fdbf03ab60d13ebee7169ceab69afdf7498","datavalue":{"value":"All graphs \\(G=(V,E)\\) considered in the present paper are finite and simple. A sequence \\(d=(d_1,d_2, \\dots, d_n)\\) is called a degree sequence if there exists a graph \\(G\\) on \\(V=\\{1,2, \\dots, n\\}\\) such that \\(\\deg (i)=d_i\\) for all \\(i\\), and \\(G\\) is said to be a realization of \\(d\\) of the length \\(n\\). The realization graph \\({\\mathfrak G}(d)\\) of \\(d\\) is a connected graph which has as vertices the realizations of \\(d\\), the so-called super vertices. Two super vertices are adjacent in \\({\\mathfrak G}(d)\\) if one can be obtained from the other by deleting two existing edges \\([a,b]\\), \\([c,e]\\) and adding two new edges \\([a,e]\\), \\([b,c]\\) for some distinct vertices \\(a, b c, e\\). (This operation is called a cycle exchange.) A graph \\(G\\) is called a threshold graph if there exist non-negative real vertex-weights such that a set of vertices of \\(G\\) is independent iff its total weight does not exceed 1 (its degree sequence is then called a threshold sequence). It is known that every degree sequence \\(d\\) can be transformed into a threshold sequence by repeated operations consisting of subtracting 1 from a degree and adding 1 to a larger or equal degree. The minimum number of these operations required to transform \\(d\\) into a threshold sequence is called the majorization gap \\(R(d)\\) of \\(d\\). Applying these concepts the authors get the following main result: If \\(d\\) is a degree sequence satisfying \\(R(d)=1\\), then \\({\\mathfrak G}(d)\\) is Hamiltonian (Theorem 1).   In Chapter 2 degree sequences are characterized more detailed by partly known theorems and lemmas and there are given some properties that are used for the extensive induction proof of Theorem 1. Chapter 3 contains a somewhat stronger version of Theorem 1 (Theorem 7).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300907$91E8AE85-761D-4FF6-8BAC-F9097A623452","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300907$B4B8ADFE-E293-4859-98FE-D35B93FDB184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300907$837E8CBC-7BE0-4925-A70A-961E0BFA9D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300907$43215287-624C-4EBA-AC56-1E19C8AD4BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300907$189CABF5-E351-4842-8BFE-F723F3ACF221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300907$A26FDA1C-E816-4516-AE4B-A555A691CDDD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bab5f834287e9febd2ee78d87338832fa7f88333","datavalue":{"value":"1331375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300907$B45BDE45-CF7E-477F-A7A1-65B202BF2B17","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f03f51a5aef98e8992373f4f78c794431f5683d","datavalue":{"value":"Hamilton graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300907$D6DA484E-CF73-472A-BF6A-075DAA9A79B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"583ae4a782a4b0f5bc359c7b8eed7e3d923f41c3","datavalue":{"value":"degree sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300907$C9DC056B-7917-4240-A06E-E40BC696A427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c07f2ef2ec73460fa191477283ea7077ac203bbc","datavalue":{"value":"realization graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300907$FC9F0942-0C39-40FE-AD44-AF4FAC245004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc2d3361c3f9ec15d0dca609605d04810e67ba5d","datavalue":{"value":"cycle exchange","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300907$A5515486-9652-41EE-8C5F-F11B3FE6E12D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67b7f2b7d313afc14e0737023f53318c1fc147e8","datavalue":{"value":"threshold graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300907$1DB4CF66-6BDC-46AA-BDB0-A50C3D9BE254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba94b577bdff6a0eaba5956d5f9ce18d15466926","datavalue":{"value":"threshold sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300907$0D630F0E-441A-4CE7-A78A-ACA768FE179F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4082d38e6f948cb8371fb487008587d6cf7b744f","datavalue":{"value":"majorization gap","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300907$FA0C8942-4DC8-4E0C-A5A5-4846671B79E3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$A0F83DE6-1DCF-4C74-8078-F94BC2D22120","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$7D1FEFC6-1CC7-4A0C-8A61-D8192082A097","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"59c010396f617ce0f28ac9ba67eadedf392b7d53","datavalue":{"value":{"entity-type":"item","numeric-id":1322868,"id":"Q1322868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$3BFE17CE-FEFA-4321-9EB2-A2ADD0AB8C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$0C367FAC-5EAC-454E-BA0F-43CEE33EDDB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d66b668d62d8680416f5ca30a5fcd0415362617","datavalue":{"value":{"entity-type":"item","numeric-id":1146695,"id":"Q1146695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$FA2832D1-71B3-4BA1-8D9B-2ACE911AFA01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f3be34444b87e94060eeddaad78e0c69a90fd2","datavalue":{"value":{"entity-type":"item","numeric-id":4165164,"id":"Q4165164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$66AAD70F-F24E-49FD-A78D-EBD65550097B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd47930f1b3201b92c88c8d229fd91955ad4b55","datavalue":{"value":{"entity-type":"item","numeric-id":5341587,"id":"Q5341587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$3DE16564-8BCC-40CE-B170-72E9B4694523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5286789daa019431eaab7c0193bf416f4098d6","datavalue":{"value":{"entity-type":"item","numeric-id":3964623,"id":"Q3964623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$972EB7C6-0218-4CB6-AAE4-20B0AD0353F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$C32DEC5A-AA50-4E87-B6C9-6AA1E18FBF1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ab81079a2db277b12693d5603e31ff517ec3443","datavalue":{"value":{"entity-type":"item","numeric-id":5812325,"id":"Q5812325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$0F81F9A6-DED3-49D8-B1AF-BBB0FC56FB72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41cc6a286064615a5226bdd0939f0f85a946c13e","datavalue":{"value":{"entity-type":"item","numeric-id":1167741,"id":"Q1167741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$95B1F3ED-F968-49B5-B093-E7D883E3FC19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9f4073089697e1fc63ae825e6b382086cc1fa1c","datavalue":{"value":{"entity-type":"item","numeric-id":2562798,"id":"Q2562798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$40788D59-DB02-4405-9310-0D1AD8CD1A83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da38422b824e5583cde5021d90cc55b2e0ac31a8","datavalue":{"value":{"entity-type":"item","numeric-id":1329809,"id":"Q1329809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$AB90E854-CFC1-4D2B-9A4A-C409690C7606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e7809e1cfc8578c0a89f99c89633690812e9e3f","datavalue":{"value":{"entity-type":"item","numeric-id":3358771,"id":"Q3358771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$E602B5BE-250D-4B8E-AAA5-F4330472DF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d1d5524b91a030cb506c147be19b598758c8009","datavalue":{"value":{"entity-type":"item","numeric-id":1899209,"id":"Q1899209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$1AB674E4-0156-4E3A-A931-F57E15BDEF79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c312a421e5a427a6cee97a32e31abe2344692e52","datavalue":{"value":{"entity-type":"item","numeric-id":5904415,"id":"Q5904415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$D788D8F3-2589-4E8B-B4C0-AFF369D828CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d3f0f9152c64464360f19c8ebe9d0acbf3b8eed","datavalue":{"value":{"entity-type":"item","numeric-id":2554701,"id":"Q2554701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$6E6BC209-310A-45F1-A5F5-10B8E291B92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f2da8b49713b38e428a50ec2bd7a5f208e823e7","datavalue":{"value":{"entity-type":"item","numeric-id":2555857,"id":"Q2555857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$3B8469F8-3270-4F85-870C-336DE3910BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d2f17e0494f55a062059bdd21fc735a1cedfe57","datavalue":{"value":{"entity-type":"item","numeric-id":4294622,"id":"Q4294622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$5F9DF2A6-529E-4803-811E-9DA7405C4AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aea525f2b61255e55f9dc694e43d9b85900aa48f","datavalue":{"value":{"entity-type":"item","numeric-id":584289,"id":"Q584289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$D2AA696A-3F66-4089-B945-0BDF47BB3143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2302fbb641ccf63a80ce247913368487ac73e24","datavalue":{"value":{"entity-type":"item","numeric-id":3910567,"id":"Q3910567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$40688AFA-F44E-4FA7-B531-53F579E52E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"294beb75b1a1ec737c0d31f05964da802f440c57","datavalue":{"value":{"entity-type":"item","numeric-id":3978366,"id":"Q3978366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300907$749A5564-04DB-470F-9BE6-8B7E4407BD97","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3d165a80196ddd57be58097e35bdeb3f7acf2a9","datavalue":{"value":{"entity-type":"item","numeric-id":1322868,"id":"Q1322868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afdc298435934350a5f030f8f53ae579cfd9fec4","datavalue":{"value":{"amount":"+0.8302837014198303","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300907$3D8190CF-AA51-44A7-9241-03D689657F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c9a897d5461dae2a6e724d425ddcf6967ff0c55","datavalue":{"value":{"entity-type":"item","numeric-id":284753,"id":"Q284753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5eb56c7991586d0d94281191a5b5b539419af65","datavalue":{"value":{"amount":"+0.800590455532074","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300907$79B78859-942E-4D9C-A1AD-33F4C53BC9F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce93195ef646cff52b159f1a855a37561fcfe7b6","datavalue":{"value":{"entity-type":"item","numeric-id":584289,"id":"Q584289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecebc6191e9bdd671c3b18fd78cfb2ca45e5b708","datavalue":{"value":{"amount":"+0.7767781615257263","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300907$6D63F932-4507-4A96-B2FC-06A4D31960CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f12e4271f69221ac0bf39fd2f139b77c5ddc7e6","datavalue":{"value":{"entity-type":"item","numeric-id":1080870,"id":"Q1080870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdbd589a6fa9349ede7e3c845d27326b3b3d52bf","datavalue":{"value":{"amount":"+0.7756118178367615","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300907$E65B5E52-BA17-4A05-BB19-9FAF422D992C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1300907","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1300907"}}}}}