{"entities":{"Q2368920":{"pageid":2379663,"ns":120,"title":"Item:Q2368920","lastrevid":72619827,"modified":"2026-04-14T06:07:26Z","type":"item","id":"Q2368920","labels":{"en":{"language":"en","value":"A degree bound on decomposable trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5020335"}},"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":"Q2368920$90D7AF39-E796-491F-920C-89ACD55EE2B0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"41b83d5542441684238aeffef3c7974d8d08b075","datavalue":{"value":{"text":"A degree bound on decomposable trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2368920$13940EEA-05E5-426F-ACA8-D922AD89A614","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cb83931cd9ce38427d15a7243416db685451cf0c","datavalue":{"value":"1092.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368920$C53AB08C-9580-4414-A5A7-C09EC030C9EB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"97aff449d8605a092d1a036d9ff7ec3f35e80cbd","datavalue":{"value":{"entity-type":"item","numeric-id":547280,"id":"Q547280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$F2E47BEE-8D03-4869-BDD9-AAF70569851A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d560cebaa1e423a6e252783aea36eab023e51f8e","datavalue":{"value":{"entity-type":"item","numeric-id":705132,"id":"Q705132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$A8234A0C-21DD-44C1-B830-8D64876B7549","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$64616581-3AEE-4F2F-83B5-699F27A51D8F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8728e91b2b3c919aca654c671fc4eed9ec21fc4b","datavalue":{"value":{"time":"+2006-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2368920$8C11D69F-39EE-4D86-82EC-0BBB66E65ECC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"869093ab3c2a64d71ac52a437e3977802369c8da","datavalue":{"value":"An \\(n\\)-vertex graph \\(G=(V,E)\\) is called decomposable if for any partition \\((\\lambda_1,\\dots,\\lambda_p)\\) of \\(n\\) there exists a partition \\(V_1,\\dots,V_p\\) of \\(V\\) such that \\(| V_i| =\\lambda_i\\) and the subgraph induced by \\(V_i\\) is connected, \\(i=1,\\dots,p\\). The main result of the paper is that decomposable trees have degree at most 4 and every vertex of degree 4 is adjacent to a leaf. Other results include some families of decomposable trees, and some complexity issues. In particular, a polynomial algorithm is given to decide whether a multipode (a tree with only one vertex of degree larger than 2) is decomposable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368920$1AE7FC51-3202-43B0-B466-307BD109A93F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f12e1eb1be75d4426df498c29926dc868c2e1814","datavalue":{"value":{"entity-type":"item","numeric-id":187114,"id":"Q187114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$6F75D9A2-93D9-4D5E-8754-BACF9E19ABFD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368920$3A59E12C-5948-4C02-AFA7-BB7B57E2375A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368920$57D725AE-D2C4-460B-80F0-24C39DD8BED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368920$D34D6C57-6792-47EC-88BC-59ED94966C7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58d33fcd5e5cb8a52812aa5e4a2f3f30b5cf0e30","datavalue":{"value":"05A17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368920$0AB126AC-061C-48F9-BF08-F414914FB384","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c455e04b2e7171d6c6740485cd1aa0396adfdd0b","datavalue":{"value":"5020335","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368920$D0B9D77E-E39E-4F3A-B5B4-0350AB9AE7F3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1e625afea5b1a633df9fe58ad43c2d03e075ec","datavalue":{"value":"tree decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368920$F7C682E4-49E3-4FEF-8B6A-8954058DD060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77c6674ab33e589248d9585faf6d7eb15c027e16","datavalue":{"value":"integer partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368920$7E94EBDF-6FBE-4A3D-9072-F6FFBE42C26E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a4e152411e1a440272710f7a5a6ed494f898a11","datavalue":{"value":"decomposable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2368920$921F455F-B73D-4E76-B24C-58CF59A89820","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":"Q2368920$6F7A0A02-2574-48FE-BDC2-783906941D50","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d856e4fcba0e398df8661668461eb561f6c16af5","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.01.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q2368920$6F555A81-5626-4FAA-BC36-CFE9B268FEA5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"78521d7e15165c2c50c43476fc41ee1824ff4ef7","datavalue":{"value":"W2121217162","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368920$7FE67153-3B02-4C6F-AE76-A0CF3029ED96","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e0a936d29cdb004405e9ceab9ae0698c1fa987d","datavalue":{"value":{"entity-type":"item","numeric-id":4321931,"id":"Q4321931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$47D90A4D-25DF-4387-B62B-64353511F0EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c07619882b16c22e5ad8464e7a0d0c6492ece4c4","datavalue":{"value":{"entity-type":"item","numeric-id":1613342,"id":"Q1613342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$2351150B-D8C7-4FBD-B0D6-19CA06BA8AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f091a2487faa4320a607c7fc5ddd1d40ffc78957","datavalue":{"value":{"entity-type":"item","numeric-id":5615282,"id":"Q5615282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$2BD6664C-D9BD-4922-A6B1-46E300C0B8A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eba7b828a0468dc2dff7f6cb527aea9fd8fceb22","datavalue":{"value":{"entity-type":"item","numeric-id":3708853,"id":"Q3708853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$53EE7919-7219-4BEE-A4F5-30F8BAF296D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41ab95cfd69e10430c9e72fb53fae7f5a4250a3f","datavalue":{"value":{"entity-type":"item","numeric-id":4947393,"id":"Q4947393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$DF6CB5FB-3A30-4D24-AE93-7A782777B399","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f66b4844bcb79a520b665f58fdec673994d537","datavalue":{"value":{"entity-type":"item","numeric-id":4393480,"id":"Q4393480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$F2402A53-6ECD-40B9-8419-10E4BE3828B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$B8F8DD2D-5B39-4BE4-9254-D45EAD91C88B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"691fb33383d3e4d33d4b849110fc64490ac7d54a","datavalue":{"value":{"entity-type":"item","numeric-id":5481324,"id":"Q5481324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2368920$3352AED3-AE21-4543-BC87-A978CF5A85A3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"218898df7167c5a79bf9ff5d6215cd3ef5296d66","datavalue":{"value":"10.1016/J.DISC.2006.01.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2368920$E1C9A31E-CEDE-4F5B-AFA2-D9A899F2E604","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bb187823b36fea5143c4011439d2aea614fa43e","datavalue":{"value":{"entity-type":"item","numeric-id":1043555,"id":"Q1043555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"047fbedfab00f5910a9a72db437d32998197da01","datavalue":{"value":{"amount":"+0.8881279826164246","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":"Q2368920$689D0C7B-75D4-4DE1-8001-CA0BF076DDF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbef2fcfa3aaa145315ab9a24981b88c21ff1d5b","datavalue":{"value":{"entity-type":"item","numeric-id":986542,"id":"Q986542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4611595f5b66bacf88b5cd9616a7ae912bed3937","datavalue":{"value":{"amount":"+0.8433698415756226","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":"Q2368920$70A9EEEB-7766-4019-BAEE-5CC764C00C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7675371095d51fb9a9a32c0c3f474cf0c6e3a32d","datavalue":{"value":{"entity-type":"item","numeric-id":1613342,"id":"Q1613342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7403062d28b218696eb9a64d524f40afa253c510","datavalue":{"value":{"amount":"+0.8165462613105774","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":"Q2368920$37067FEF-7888-4030-BD45-8F35166CC0F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e4f9a813a0242c503215b8b97979281a81dac1a","datavalue":{"value":{"entity-type":"item","numeric-id":3320412,"id":"Q3320412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"076ad1b1a273c3a9f3f46d9e6a7984ea324edaa6","datavalue":{"value":{"amount":"+0.815554678440094","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":"Q2368920$27A0F45C-4E1F-418A-A15A-370C4A3869D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8706f29d4974b98cdbcdf5bd88817a8feaef39d2","datavalue":{"value":{"entity-type":"item","numeric-id":5481324,"id":"Q5481324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec882cc0069b4536e1d2e5c92cbcc00f76b45acf","datavalue":{"value":{"amount":"+0.7815465927124023","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":"Q2368920$36C26EE5-76E8-4F69-B3CD-7508E3B9113A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A degree bound on decomposable trees","badges":[]}}}}}