{"entities":{"Q1322016":{"pageid":1332766,"ns":120,"title":"Item:Q1322016","lastrevid":67173069,"modified":"2026-04-12T15:47:03Z","type":"item","id":"Q1322016","labels":{"en":{"language":"en","value":"The color-degree matrix and the number of multicolored trees in star decompositions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 562404"}},"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":"Q1322016$7DD75BF6-740F-4703-9CE7-A17E1E32C1D3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bdd536208f58899bdbe261a3be09bd11d5f17107","datavalue":{"value":{"text":"The color-degree matrix and the number of multicolored trees in star decompositions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322016$89C8E42F-200C-4051-BDA6-00193DD7707A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2de1f8f21bba403b38b090dd0883fefa25555200","datavalue":{"value":"0794.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322016$31102301-3D2B-4852-8041-8B8A0649DD42","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b708f11c7951e77c2611a0022e9f2eba2b959fe4","datavalue":{"value":{"entity-type":"item","numeric-id":423158,"id":"Q423158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322016$3B66F928-7D8E-454D-9CB3-F48EF2F7AE72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"35f78ec020189a61746255d01efb9a398cb1a35d","datavalue":{"value":{"entity-type":"item","numeric-id":580370,"id":"Q580370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322016$233B5CA9-0071-485C-B6E5-1CC079494AD0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322016$DDD94991-4D1B-4B5D-9D77-CBCEE54160C0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a511c8ef0b44d10360e4b2f51c22be5a4c1a9ced","datavalue":{"value":{"time":"+1994-09-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":"Q1322016$56408547-1ED3-4F46-BF06-B9A2D9CFD129","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e4b25c14fb72507a22b1d8e540aa2bb82c19e778","datavalue":{"value":"In a previous paper we investigated the problem of counting the number of multicolored spanning trees in biclique decompositions. In particular, for acyclic decompositions we found the minimum and maximum numbers of multicolored trees. We now introduce the color-degree matrix \\(C\\) and show that the number of multicolored trees is bounded below by the determinant of \\(C\\) with a row deleted. In fact, we get equality for acyclic decompositions and for star decompositions. Unfortunately, for arbitrary decompositions the ratio of this determinant to the actual number of trees can approach zero. We find that star decompositions on \\(n\\) vertices are in one to one correspondence with tournaments on \\(n-1\\) vertices. This allows us to determine that the minimum number of multicolored trees among all star decompositions of \\(K_ n\\) is \\((n-1)\\)! and the average number is \\(((n+1)/2)^{n-2}\\). We bound the maximum number of multicolored trees between this average and \\(\\lfloor n^ 2/4\\rfloor^{(n-1)/2}-\\lfloor(n-2)^ 2/4\\rfloor^{(n-1)/2}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322016$EBDCBF94-11F0-42D3-BA45-541C8BC61D1A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322016$61936AAE-D86E-4980-8C20-21189E80453E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322016$687D0533-5407-487B-95EF-E074A02B6FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322016$63F85EB8-B778-445F-A79A-E2C4C4DA379A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322016$78B57429-612E-4D1A-90F1-E221E45331DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322016$1AED1489-EB96-4F2E-80C9-E91CD8745CC5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d077e16b4cf8e71f25473b9a849766cad7e4413b","datavalue":{"value":"562404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322016$E71442E7-1D22-45BF-8F4F-F9DD9C0692E1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5c44fa1e0363260b6f288e0b401fc69b04cda0c","datavalue":{"value":"multicolored spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322016$7197B598-A78E-41AF-A7A7-5C7E1428EFB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d65d96e26ba7f502206a0841e88ddfd329fc1d64","datavalue":{"value":"decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322016$0F53A8F1-DB32-4B2C-A426-8C227C61E0A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"833bbd53d55c49da007cbcafddc533d25bd4bba5","datavalue":{"value":"color-degree matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322016$CAC70379-9660-4F44-B5F7-7D17E315D9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8dcff222ddaefc8a93b0bb6468d6486e2539807a","datavalue":{"value":"multicolored trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322016$85C57DE0-9AE8-467D-8CE3-DAAEE13F6699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ae732e04d688c1a23e3e119224998ad36678e35","datavalue":{"value":"star decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322016$5513224B-330D-49D7-9651-CD0C9D0AC731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d49cfb1e4c39c6acbfd1e6a37751a0100c25d4","datavalue":{"value":"tournaments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322016$9A0A5CA2-F3BB-4129-B9CA-3325F96F313F","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":"Q1322016$3F8C723C-B992-4ED4-BA63-45A84D406977","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e410e1220c42c0c17eea48afbd0bcd9a8ede4863","datavalue":{"value":"https://doi.org/10.1006/jctb.1994.1014","type":"string"},"datatype":"url"},"type":"statement","id":"Q1322016$616DE704-86E6-439A-AB29-2ACDE63FA859","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e0f74e302887f5b08b122af2a6a413915a844e68","datavalue":{"value":"W2084584315","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322016$46486F34-E8F7-4056-9F12-A7AEDEF5C081","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2985e8880c861a8a7e3db04bc9f81a0deb51a1f1","datavalue":{"value":"10.1006/JCTB.1994.1014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322016$33F3EAA8-19D6-4B16-85CF-F9A7BB7D0CB5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa3a9faa35278728b843fdbea7b4b59d7c259879","datavalue":{"value":{"entity-type":"item","numeric-id":4028276,"id":"Q4028276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d39d44a091c8908f383dc6d0e42a1e2522d1ce99","datavalue":{"value":{"amount":"+0.92581266","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$FB42A051-43F6-4993-BAC0-4ACD98D12AE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bf11459d0350d8e067a16c255401dd5b0e5ba67","datavalue":{"value":{"entity-type":"item","numeric-id":4989822,"id":"Q4989822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffcf71edf043c5e9a5efed88c1be35f4bdb32d82","datavalue":{"value":{"amount":"+0.9000093","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$FE5C9E49-B375-4464-A077-FC7398A46A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c1eaf7ae78119d86dc6a2fac729dbe562844904","datavalue":{"value":{"entity-type":"item","numeric-id":5010149,"id":"Q5010149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aed5b9c18101e79f2406cb8b5aa9e9dba89b37b5","datavalue":{"value":{"amount":"+0.8946929","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$111BD442-B84A-48AB-8704-EE70E6B90EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8914a2d5d899fbb43a5ca65ff72261179b0aec17","datavalue":{"value":{"entity-type":"item","numeric-id":1186126,"id":"Q1186126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76b4d3fdd035336f1db55c618b28d06b78839f30","datavalue":{"value":{"amount":"+0.88663447","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$E8F37E1E-D41D-45B4-95EC-9BCBB0DA1FC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"309a51c18e343dcd231d4121d81210cd36350eab","datavalue":{"value":{"entity-type":"item","numeric-id":4364807,"id":"Q4364807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de5fdcfede55e1f9933efc8854ed3e9201ac6496","datavalue":{"value":{"amount":"+0.8863792","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$97372472-5DCF-4DE6-8FE4-6BFA6A6D8542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8be43a96da948f9ddd372d8645120ec3ea57ebbd","datavalue":{"value":{"entity-type":"item","numeric-id":5898715,"id":"Q5898715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0d767ac6e22d7f1f1027fa2348950fbadd940ca","datavalue":{"value":{"amount":"+0.8851245","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$EEFF2398-195D-46A7-B609-D0AB5BAF4BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e70c7425dd28647a4990221155adbea99a066371","datavalue":{"value":{"entity-type":"item","numeric-id":5904060,"id":"Q5904060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a53b2a57101f704f38db359b494481706cb06f76","datavalue":{"value":{"amount":"+0.88512444","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$047FD089-6CEB-48FF-A6A7-DFA591A92ADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"261d16389f3df252eb4b6ef157ea043d8c528d07","datavalue":{"value":{"entity-type":"item","numeric-id":5377364,"id":"Q5377364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be3692abdc38ab3ae18189dd370c06981ba4a992","datavalue":{"value":{"amount":"+0.884041","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$66031AF0-5272-4BB9-A961-2C4B8DFF44C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a38e26d520fc1f349643823f3c127e15e426b722","datavalue":{"value":{"entity-type":"item","numeric-id":4691430,"id":"Q4691430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be3692abdc38ab3ae18189dd370c06981ba4a992","datavalue":{"value":{"amount":"+0.884041","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$640C07DF-7071-434E-A8C4-4305821B038A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32bb51f9e6e86cd18aceaaa1b98f622a2cdcc5ac","datavalue":{"value":{"entity-type":"item","numeric-id":4708601,"id":"Q4708601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cd76dfd0ff54d4805bb4476bf6f4854817b4b73","datavalue":{"value":{"amount":"+0.88357","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322016$E78F267D-A061-4B56-9B89-CEEEA93B8259","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The color-degree matrix and the number of multicolored trees in star decompositions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_color-degree_matrix_and_the_number_of_multicolored_trees_in_star_decompositions"}}}}}