{"entities":{"Q2175807":{"pageid":2186550,"ns":120,"title":"Item:Q2175807","lastrevid":57766023,"modified":"2026-04-02T10:49:40Z","type":"item","id":"Q2175807","labels":{"en":{"language":"en","value":"Packing tree degree sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7195263"}},"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":"Q2175807$5330008E-7F1F-4D07-9801-58AF2C3B715E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fed89ca43ad4e0cc4788da06d732d1974f525488","datavalue":{"value":{"text":"Packing tree degree sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2175807$0CD75ADF-8C7A-46DA-8A86-72C26014DD21","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b382b53681b0a471f772f9c22830232c749a4e91","datavalue":{"value":"1486.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175807$8874AD95-6CCF-4FC3-BD58-49197A43A6F8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9299e29b04ab0258fe17c97f4ec67434c04292b2","datavalue":{"value":{"entity-type":"item","numeric-id":2175806,"id":"Q2175806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$8F37449C-C341-459E-BA1B-2375A1D4333B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8aed1e756193529fe6de70fb931bc03448cd63ae","datavalue":{"value":{"entity-type":"item","numeric-id":2145878,"id":"Q2145878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$F77B7F7F-64F2-4336-89DA-C629B6022B5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aceb36402978b7b9f7bbe2418819becc88d7d8f1","datavalue":{"value":{"entity-type":"item","numeric-id":253273,"id":"Q253273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$72052222-60FB-47E2-AF5D-7A874BA153AC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$1B09F033-C900-4446-8D87-3CAFE317A92B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dde1b11a90e0e18f0bcca3b838f9ec9fe003c840","datavalue":{"value":{"time":"+2020-04-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2175807$A9009017-EA29-4BF7-AD47-435C4915207F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8226b50e23db0fcdf3db42416d8e9aece81141a1","datavalue":{"value":"https://arxiv.org/abs/1704.03148","type":"string"},"datatype":"url"},"type":"statement","id":"Q2175807$DBFFFF84-22DC-4E65-A303-AA6FC6C06546","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c36018e2571e37adde9f3e9d09ea794c27a81edc","datavalue":{"value":"A degree sequence is a list of non-negative integers, \\(D = d_1, d_2,\\dots, d_n\\). It is called graphical if there exists a simple graph \\(G\\) such that the degree of the \\(i^{\\text{th}}\\) vertex is \\(d_i\\); \\(G\\) is then said to be a realization of \\(D\\). A degree sequence \\(D = d_1, d_2, \\dots, d_n\\) is a tree degree sequence if all degrees are positive and \\(\\sum_{i=1}^n d_i = 2n- 2\\). A degree sequence is a path degree sequence if two of its degrees are 1 and all other degrees are \\(2\\).  The paper consideres the problem of packing tree degree sequences: given \\(k\\) tree degree sequences, do they have simultaneous (i.e. on the same vertices) edge-disjoint realizations? Also it conjectured that this is true for any arbitrary number of tree degree sequences whenever they share no common leaves (degree-1 vertices). This paper gives a proof for \\(4\\) tree degree sequences and a computer-aided proof for \\(5\\) tree degree sequences. The conjecture for arbitrary \\(k\\) is also considered. It is proved that \\(k\\) tree degree sequences without common leaves and at least \\(2k- 4\\) vertices which are not leaves in any of the trees always have edge disjoint tree realizations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2175807$E7A216DF-22FE-42B6-A4E0-0C168295622C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4855149d85687285dbc61d1f53c172412a1eb57b","datavalue":{"value":{"entity-type":"item","numeric-id":659761,"id":"Q659761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$CB4C9CF7-AC6B-4803-9C42-FB5B7A4CC42B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175807$F130AF96-2028-4AF2-8118-D303A657DC03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175807$CDBC1BDE-A050-44AC-8886-DF0FA2583446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175807$99C36DCD-2D6E-4388-83E2-FC96907092D7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"96bc3ad48493081e3b1a3069e57e4c99e5a0a21f","datavalue":{"value":"7195263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175807$39C331E0-95DD-410C-B1F7-740907996946","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"151b8d7fcdc6fc6d73265744ac86c853512ce9f9","datavalue":{"value":"degree constrained edge partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q2175807$D5E5E696-6E1A-4721-AE0A-BF224482A523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e30d027f2b324bb3ff51568d07e9b133df4db1eb","datavalue":{"value":"tree sequence packing keyword","type":"string"},"datatype":"string"},"type":"statement","id":"Q2175807$5D3F0C01-154B-4FD2-9B09-2D164AC5B689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d38dfce1450c2e6e12520ff96f70bf75c89bdfd8","datavalue":{"value":"rainbow matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2175807$48BBB6B2-50B1-4677-8321-1983631CEBB4","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":"Q2175807$41265122-81A8-4BEC-9BFA-0B76DCCF0787","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8906f196ff8e53d6c7ce7a9d03110e53140b8a75","datavalue":{"value":"W3010918251","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175807$8F511571-B707-4C99-A8C2-6D0AFA75775C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c534b47626d80e2ae8ec59b890fe041e3586f27d","datavalue":{"value":{"entity-type":"item","numeric-id":3514485,"id":"Q3514485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$F824E6A7-02ED-4BCD-BEC6-23211D3FAFF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"950f8701c69d22f43cfe804b62f85db86b8887a4","datavalue":{"value":{"entity-type":"item","numeric-id":3627968,"id":"Q3627968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$34FD056A-DF26-4CC8-A6E2-A9A89BBA356D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b72061433dc652c12f78050faaaca363f4b15a34","datavalue":{"value":{"entity-type":"item","numeric-id":2888877,"id":"Q2888877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$3A7E0C1E-6117-4D87-AD3D-78624B87690A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f91dd00fc9ce6d20cfcceb9196c6926c42e28f9","datavalue":{"value":{"entity-type":"item","numeric-id":1106246,"id":"Q1106246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$F728B815-7EF7-4FD9-A544-EA07D9178F46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b11619a2fdb2060ffa8e3ea1e139344e1615e32","datavalue":{"value":{"entity-type":"item","numeric-id":3287781,"id":"Q3287781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$1AF083CA-CB69-4AB2-8A96-618FAF7A1AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff84ae02804e61976c3b20bbafec2fbca9afb8e","datavalue":{"value":{"entity-type":"item","numeric-id":617894,"id":"Q617894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$9AE1BC88-4F40-4CB5-BA88-4DC9DDE96A34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6d065dc02799af10f1abafe94d346ed938e871b","datavalue":{"value":{"entity-type":"item","numeric-id":298973,"id":"Q298973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$87AAACC5-A080-40A3-8915-EF9EFC808A06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"873dc7bf67e447db4d96edba9b1d14a1df75d9ab","datavalue":{"value":{"entity-type":"item","numeric-id":1394360,"id":"Q1394360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$DD6B78C6-2150-4153-9ED3-630610469D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41728e2f92c4560b798081c73ce07f00fe93f598","datavalue":{"value":{"entity-type":"item","numeric-id":5654064,"id":"Q5654064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$854C2284-528B-438E-B96C-F2E3652F6B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5ad4d308b8d95db202675d9759af62ea3caf522","datavalue":{"value":{"entity-type":"item","numeric-id":4044593,"id":"Q4044593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$8FCC021D-4368-4EC9-B5B2-6730BA5F63EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08117d17bbd89f0c8fa568ffb41ecf230f70d13d","datavalue":{"value":{"entity-type":"item","numeric-id":1003744,"id":"Q1003744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$243301DC-DF1B-49E1-BC3A-A76E4BD806A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a21dd26afe75bfcbb91167d002f5ef571b3676f","datavalue":{"value":{"entity-type":"item","numeric-id":1874382,"id":"Q1874382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$1BC48CC6-55C9-42F4-A79E-5453EBE291CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"519d233ef87c3baea6972dcac9c04b65478434e6","datavalue":{"value":{"entity-type":"item","numeric-id":1199499,"id":"Q1199499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$4D80E596-88DE-4EA2-8489-82123266DDA4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3573584d849448a8ed6bca6d075d078d5bb28dc6","datavalue":{"value":"10.1007/S00373-020-02153-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2175807$6C7E664B-F40B-4B1F-8DA9-709D2CE7471E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27e3ca4ac2b51df557e53b0c4a0e155595ebbe0e","datavalue":{"value":{"entity-type":"item","numeric-id":2341721,"id":"Q2341721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c2edf23e4ec72af0fe8cc9052fa0607732b9e62","datavalue":{"value":{"amount":"+0.8040854334831238","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":"Q2175807$E272D039-EC8E-489A-91DA-DC2C0F946F0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd3b553341caf0722f86b3f4644a49a52a4702a2","datavalue":{"value":{"entity-type":"item","numeric-id":4344220,"id":"Q4344220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f411ff510f5d5ed8839085f71485a41ab0429ae7","datavalue":{"value":{"amount":"+0.7953051328659058","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":"Q2175807$853015F1-60AE-4998-AF42-9114237E5FE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"037b132806685120aae69d7cdf14b8103f75ec57","datavalue":{"value":{"entity-type":"item","numeric-id":642969,"id":"Q642969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90f9ca8410177330b56f2807aee0be7cf47f84f1","datavalue":{"value":{"amount":"+0.7950744032859802","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":"Q2175807$E1B8D740-6794-4E06-B952-55D01EC5CA0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7f8b4872c3cc6b0a9c34b0c708c1bc4db126b0e","datavalue":{"value":{"entity-type":"item","numeric-id":5408605,"id":"Q5408605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8b3b9fb05ce279364a15100b166b67b9f6da481","datavalue":{"value":{"amount":"+0.7946874499320984","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":"Q2175807$A65049D9-A317-40A1-B85B-C976912AC4EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3ec1691dc3ce9445ae7ad59f46e3c6582cb81d1","datavalue":{"value":{"entity-type":"item","numeric-id":2026343,"id":"Q2026343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"163f550e823eac98b9b74921383725aa9ee81284","datavalue":{"value":{"amount":"+0.7863231301307678","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":"Q2175807$29F25A16-2A25-438B-A551-906BED382C04","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2175807$D628240D-7CF1-4245-8D8D-36AC9929B651","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2175807","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2175807"}}}}}