{"entities":{"Q1060225":{"pageid":1070977,"ns":120,"title":"Item:Q1060225","lastrevid":69756930,"modified":"2026-04-13T09:11:10Z","type":"item","id":"Q1060225","labels":{"en":{"language":"en","value":"Isomorphic factorizations VIII: Bisectable trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3906517"}},"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":"Q1060225$BD490C96-8F11-4846-8D91-3FC30A43AD07","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8e1c1e845b7268dd1d8596c41189d115db4f5914","datavalue":{"value":{"text":"Isomorphic factorizations VIII: Bisectable trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1060225$698D9D67-14F9-4CD6-8C6A-01BCC0545B3C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"663b3165277b4755ed7bb9086d24f365b4484b70","datavalue":{"value":"0568.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060225$733D3B87-4B1A-4D93-9D8F-C229D7E59435","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7fd6924e38d030620819acf43d572512c72eaebe","datavalue":{"value":"10.1007/BF02579217","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060225$FA22B7D7-0F93-40A7-AEBF-FDCB85B397C8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06d35deff844ad14009ec831196ab8a1bd18feeb","datavalue":{"value":{"entity-type":"item","numeric-id":293362,"id":"Q293362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$4C600C75-2834-493E-BC91-74FEB195525C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9761403fcee52ad05d4a9965da0de7611014af85","datavalue":{"value":{"entity-type":"item","numeric-id":787983,"id":"Q787983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$F650E56B-08CD-4A97-9087-7E8D7416AB5D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$78852283-7AEB-49DF-845D-36CEC02B0371","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1060225$9D25FC56-F6CE-4103-9FE1-9FA5FF29D27A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bbda9be2b7a3bc7b258b176d8e8371d9e8682646","datavalue":{"value":"A graph is t-factorable if its edges can be partitioned into t copies of a common factor subgraph. When the original graph is a tree T the common factor must, of course, be a forest, but if the factor S also happens to be a tree we say that T is t-sectable. The authors show that given T and t there is at most one candidate for S. This fact leads to a linear time and space algorithm for determining the t-sectability of T. Furthermore, for \\(t=2\\) a bisectable tree T also has a unique bisection, but for \\(t>2\\) there can be inequivalent t-sections even though all use the same factor S. This extra structural knowledge for bisections allows the authors to use standard enumeration techniques to count the number of bisectable trees and find asymptotic estimates. The reader should be alerted that in the final half page the letter n appears in several formulas without explanation, but it appears that n is identical to p. To contrast the algorithmic difficult of t-factorization as opposed to t-sectability, in the next article in this series, Isomorphic Factorizations IX: Even Trees (to appear), \\textit{R. L. Graham} and \\textit{R. W. Robinson} show that deciding whether a tree is 2-factorable is NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060225$F42ECC82-945A-494E-8EB7-63AC7CCB4D74","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060225$B4721017-4851-4375-8B06-A1481C7DDBE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060225$6A7EAE96-8A15-4AE5-8506-004A2200788C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060225$718A21CB-CE75-4C97-963B-2EFF7D4DF481","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e39d67c51684c365cd8476d98672cf718bee6fa6","datavalue":{"value":"3906517","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060225$7543A31D-5B29-416B-B9AB-6607BBF55E03","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"561d1741ef675acd86d3bbdf245f4c227d40a463","datavalue":{"value":"tree enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060225$A2416C14-9711-4400-A459-2A28F2817CE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd00be81ed6850004c41948decdc98ac63b7f732","datavalue":{"value":"bisectable trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060225$BC613E00-A457-46B5-B7FE-A5B35A885E13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40af369fcc8e670b50c7cc885a4bb5e1ffff9148","datavalue":{"value":"Isomorphic Factorizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060225$65CD3D5A-081A-4278-9ECE-8AAEE6736052","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7df19f0497c85a326e24971e224735a1dc68f0e9","datavalue":{"value":"Q114233778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060225$1054D1C4-B236-4CCA-B8AA-C0851C9DC269","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":"Q1060225$6E022F91-1C07-4DA6-926C-27B38A512DA0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"767177c9c2beae2d8abc0a60a160c198d5edad64","datavalue":{"value":{"entity-type":"item","numeric-id":3901534,"id":"Q3901534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$BAB206B9-A04A-4457-AABD-3C9FFA1AC6A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cff90b53746deaf40f0bd975035788d645dc76ab","datavalue":{"value":{"entity-type":"item","numeric-id":5682013,"id":"Q5682013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$FCB679D3-218D-48D6-B38E-814B830FCB79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea7a5f82133fde259a405cb5f1cb8a6c12cd2e8d","datavalue":{"value":{"entity-type":"item","numeric-id":3889089,"id":"Q3889089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$D9417103-4C5C-4A42-817E-97AD417C26BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34f94e9b0ab478fa07576025ff09963390ce7f59","datavalue":{"value":{"entity-type":"item","numeric-id":1249194,"id":"Q1249194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$BDB972A3-D837-4E06-97A2-806033875A53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"358fc9390b3b2efcaacc008fab9202e810f7f5c5","datavalue":{"value":{"entity-type":"item","numeric-id":4081275,"id":"Q4081275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$26AEBFE7-6903-4D99-B987-A2DE81D4358F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed0da87a34fdd2bacc840e6220f99da13399a860","datavalue":{"value":{"entity-type":"item","numeric-id":4159099,"id":"Q4159099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$638F5856-3581-4EEF-BE3B-8B2C9C71E189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c742a917f5f4682f5f756189a00bbe04c9c7793","datavalue":{"value":{"entity-type":"item","numeric-id":3852224,"id":"Q3852224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$996AAAC6-9F4D-43E4-8F06-EDD79F774B86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d31bd230c3d64bd6230cba9fd85bb16020a9677b","datavalue":{"value":{"entity-type":"item","numeric-id":4190653,"id":"Q4190653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$B519F613-7AE9-41FC-8DE5-B155BBBD0B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73af642b72177fe106dcb62ceb2c01108ce66935","datavalue":{"value":{"entity-type":"item","numeric-id":3875946,"id":"Q3875946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$DDB2FBD8-2DF5-416B-AC12-6BDFDFB6AF7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"814ce33b60468aefb369bf0110f04b12db83d3d5","datavalue":{"value":{"entity-type":"item","numeric-id":3852225,"id":"Q3852225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$1419174D-A549-4DE8-A5F3-F84AF62726E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75c72efb3fce6d4601c56715cf7977151523ac4b","datavalue":{"value":{"entity-type":"item","numeric-id":1218434,"id":"Q1218434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$87A5646D-3CE9-4854-8A12-64A732367FAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17da186bf31ad3fcf81808539d06732a19a3799a","datavalue":{"value":{"entity-type":"item","numeric-id":3313900,"id":"Q3313900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060225$BD98622A-A4F9-4FF6-BA9A-663A188DDA46","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d68cda8d6cb1e942214cb802de425404705a1dc","datavalue":{"value":{"entity-type":"item","numeric-id":685643,"id":"Q685643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd69987737ef0925649faf2ddd9da9bf274e6cf7","datavalue":{"value":{"amount":"+0.8051121234893799","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":"Q1060225$E4C04D3F-8881-4CED-957B-C544236F773C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"109fd2d5e28f37e464b7883727654af64a6bc346","datavalue":{"value":{"entity-type":"item","numeric-id":4337363,"id":"Q4337363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5a8b6d796b575a71111ff36d02908e711be10e1","datavalue":{"value":{"amount":"+0.800881028175354","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":"Q1060225$F2FAE2F8-C476-49CC-866F-D84F592F99AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37699346783a94d2088587427e5fe4a9a15b9102","datavalue":{"value":{"entity-type":"item","numeric-id":2739718,"id":"Q2739718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5a8b6d796b575a71111ff36d02908e711be10e1","datavalue":{"value":{"amount":"+0.800881028175354","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":"Q1060225$DD6A0230-C223-4EEE-AE13-9BA07B796927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1792b757418ccea09e86c4c5134aabadbee51283","datavalue":{"value":{"entity-type":"item","numeric-id":4014289,"id":"Q4014289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5f963e29d87a103904e6f1f9d9fdf9fc15edb1b","datavalue":{"value":{"amount":"+0.7818265557289124","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":"Q1060225$9B50C592-9B98-40BC-A75C-72A9BC4C2963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce3963d03207d9c391d28176e1867e2bca79cbab","datavalue":{"value":{"entity-type":"item","numeric-id":1200005,"id":"Q1200005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c884dd89d2d8a86996b9a0862517c4dc3bcb16e5","datavalue":{"value":{"amount":"+0.7727491855621338","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":"Q1060225$DF32D060-1AA7-4A73-90FF-1729A20BB729","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Isomorphic factorizations VIII: Bisectable trees","badges":[]}}}}}