{"entities":{"Q2200917":{"pageid":2211660,"ns":120,"title":"Item:Q2200917","lastrevid":57783162,"modified":"2026-04-02T12:34:47Z","type":"item","id":"Q2200917","labels":{"en":{"language":"en","value":"Decompositions of complete multigraphs into stars of varying sizes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7251271"}},"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":"Q2200917$44A922D7-1B01-4119-93B3-87D2C92C51CB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9b51ee3857d44f9c86754bf2a0fb8ab97c5d8cc9","datavalue":{"value":{"text":"Decompositions of complete multigraphs into stars of varying sizes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2200917$B4BCB4A4-BF86-4655-B886-2D475BAAFEC3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"19a7ee2732096604cd134feabe129198dcefdbe7","datavalue":{"value":"1448.05160","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2200917$5183A420-DD1E-489D-939A-2E6E6CDD5833","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c879a398046aea4730f7b7699c1380d53c11b5b4","datavalue":{"value":{"entity-type":"item","numeric-id":2197469,"id":"Q2197469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$4B941E4D-BB0A-44BE-9484-17D8967688FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bb410d3692940f7077fcb89b6fbfd8f4d3d793a","datavalue":{"value":{"entity-type":"item","numeric-id":681599,"id":"Q681599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$B8DB1592-C8D0-41EC-B5A4-1D59CD20DD22","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":"Q2200917$A74DB2C6-4477-4675-B50A-2B587FBCE9A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3f481032088037db5fde3345386df6f2ab23a065","datavalue":{"value":{"time":"+2020-09-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2200917$48E519FA-AEC7-4658-B662-E3378AECC031","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e27d29826d3ff9133d555efb5b0a29e467386cab","datavalue":{"value":"https://arxiv.org/abs/1807.10738","type":"string"},"datatype":"url"},"type":"statement","id":"Q2200917$E7CC8217-80B9-49AD-B9A9-D877E5B970B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1d3193528b9d5bafdba52823f6473a103f85d2fa","datavalue":{"value":"An \\(m\\)-star is a complete bipartite graph \\(K_{1,m}\\); for an integer \\(\\lambda\\ge1\\), \\(\\lambda K_n\\) denotes the multigraph obtained from the underlying graph \\(K_n\\) by assigning to each of its edges the multiplicity \\(\\lambda\\).  This paper generalizes to multigraphs a numerical characterization [\\textit{Z. Lonc}, J. Comb. Theory, Ser. A 61, No. 2, 263--278 (1992; Zbl 0763.04004); \\textit{C. Lin} and \\textit{T.-W. Shyu}, J. Graph Theory 23, No. 4, 361--364 (1996; Zbl 0880.05069)] for the existence of a decomposition of \\(K_n\\) into stars of specified sizes. The authors formulate a primary question, \\((\\lambda,\\alpha)\\)-STAR DECOMP, as a family of decision problems, one for each integer \\(\\lambda\\ge1\\) and real \\(\\alpha\\in{\\mathbb R}\\) such that \\(0\\le\\alpha\\le1\\): if \\(n\\) and \\(m_1,\\dots,m_t\\) are positive integers such that \\(\\max\\left\\{m_1,\\dots,m_t\\right\\}\\le\\alpha(n-1)\\) and \\(m_1+\\dots+m_t=\\lambda\\cdot {\\binom n 2}\\), does the multigraph \\(\\lambda K_n\\) admit a decomposition into disjoint stars of sizes \\(m_1,\\dots,m_t\\)?  The main theorem is:   Theorem 1: Let \\(\\lambda\\ge2\\). Then \\((\\lambda,\\alpha)\\)-STAR DECOMP is NP-complete if \\(\\alpha>\\alpha^\\prime\\), where \\(\\alpha^\\prime=\\frac\\lambda{\\lambda+1}\\) if \\(\\lambda\\) is odd, and \\(\\alpha^\\prime=1-\\frac2\\lambda\\cdot\\left(3-2\\sqrt{2}\\right)\\) if \\(\\lambda\\) is even.  Furthermore, if \\(\\alpha\\le\\alpha^\\prime\\), then every instance of \\((\\lambda,\\alpha)\\)-STAR DECOMP is feasible and the required decompositions can be constructed in polynomial time.  This theorem is proved as a consequence of a second theorem, as another application of which the authors are able to generalize to orientations of a multigraph a theorem of Landau which characterises when there exists a 1-fold tournament with specified degrees [\\textit{H. G. Landau}, ``On dominance relations and the structure of animal societies. III: The condition for a score structure'', Bull. Math. Biophys. 15, 143--148 (1953; \\url{doi:10.1007/BF02476378})].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2200917$CEF2E990-271F-4E57-B315-E08B7B4502CE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2200917$8FB9B3E2-434F-4124-9595-1686BB3ECF58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2200917$A940F850-07E1-45D3-9A2F-22D6FBC35401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2200917$32439E79-44FE-4AD9-8898-DAB43D8CCCBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2200917$998E48CB-301B-446D-9D73-F6B89218A902","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"db4583fd3ac7fa6fa253efbe6e25e9273df5af47","datavalue":{"value":"7251271","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2200917$35218DD3-E1CF-4CED-A40B-CCB56032DD1D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5eed6cf8beadefa5f78cdd2d2d6a6cb657a9a71c","datavalue":{"value":"edge decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2200917$10EE3C49-42C6-4886-A0B4-1858C5DF20C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43d9fcb3dcd5dd3e1909f3ed420a3e7cab4c7b6d","datavalue":{"value":"star","type":"string"},"datatype":"string"},"type":"statement","id":"Q2200917$9FAA7C92-6EDA-4D04-B96A-F63D1A447869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07461c31e3f30a5afb1c1c6aedc4bff7cc6aca18","datavalue":{"value":"complete multigraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2200917$11B43F65-1FA6-4810-AFF4-5346186A444F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2200917$E51F4CBF-959A-41E8-95BB-B0BE41F8F1B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1db92bc7601eaee178ffaed0103e4107bc22c468","datavalue":{"value":"tournament","type":"string"},"datatype":"string"},"type":"statement","id":"Q2200917$ED334BA2-0B58-47F3-9D4D-70508350D112","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$6A606DBA-803D-45F8-86A9-42C4BD38325B","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":"Q2200917$7664BFE8-3096-4D13-A648-05BDC4951ACC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"32131abcdbf7d18a6a6e4d02da7e4c5664cb8a5b","datavalue":{"value":"W2884040980","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2200917$2FC57648-BCA8-401A-9F27-D19BDAFF2060","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52afa7bd6bb478f700f9914e8cf74ba8028fe212","datavalue":{"value":{"entity-type":"item","numeric-id":2766428,"id":"Q2766428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$F56D2FBA-9DD3-4307-BEBE-791E17EFB25C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8701f054f591313fb9dd2b97ec59f53b967bbb0","datavalue":{"value":{"entity-type":"item","numeric-id":4063504,"id":"Q4063504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$852ECA17-AD43-4BE8-9654-0C62985DDD4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61c3d946025854b8b117217a5c741cf0b50ebb6e","datavalue":{"value":{"entity-type":"item","numeric-id":965248,"id":"Q965248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$A773ACFC-CC8E-465C-8C95-902C87BD1640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"196f57adce0ec93ee279aabcbff20b4f5322a68f","datavalue":{"value":{"entity-type":"item","numeric-id":5936091,"id":"Q5936091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$9B87A6FC-8050-4B25-A857-17DE0FA9A087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dfb964e393a6a95d57e596f9c1c29cf4d5f0d57","datavalue":{"value":{"entity-type":"item","numeric-id":684123,"id":"Q684123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$70A72412-30E6-44D6-94E8-106841980EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abb228b8e0a9b8221782f1a1717638989a2d5dfc","datavalue":{"value":{"entity-type":"item","numeric-id":5484517,"id":"Q5484517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$8AC25233-FB53-476D-B8D3-818A4A8D9404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35f1edd7ea42b0ed435668939c82b0dad4e7cac1","datavalue":{"value":{"entity-type":"item","numeric-id":472972,"id":"Q472972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$2FEA1999-D551-4E23-8AA3-7419E4FCE228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0b5f64eae3a0013043ea8bceb727c9df1b18197","datavalue":{"value":{"entity-type":"item","numeric-id":5461475,"id":"Q5461475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$D514EFA4-E3E5-4F71-AF47-A7E40AB00801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faba6bbf127f770c659496defe55ac19f28d99b1","datavalue":{"value":{"entity-type":"item","numeric-id":1876685,"id":"Q1876685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$CF125CB2-AC9B-4C3E-AA5A-9919B62ED48E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6226577d8efcf89d79bb2057f680a270163af5e7","datavalue":{"value":{"entity-type":"item","numeric-id":2876038,"id":"Q2876038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$457B7CC9-290C-46B1-A845-AB7CC7E77419","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":"Q2200917$CBE6DC3C-C905-48CD-B908-3D7BC61758CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c3481f9b886b2ea0ccc7e3206ef0b68a60f598f","datavalue":{"value":{"entity-type":"item","numeric-id":5284583,"id":"Q5284583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$DB728378-08BD-4180-8C7E-E8B2C63205F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4705240e52af4baf5d12f2e3dcbb143265280f9a","datavalue":{"value":{"entity-type":"item","numeric-id":1200001,"id":"Q1200001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$A6088DED-5B0B-4A8F-B7FF-64065DF1CC09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33aa38cb5d8b794d900dbf968c579c9640b96726","datavalue":{"value":{"entity-type":"item","numeric-id":2487986,"id":"Q2487986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$1F17F150-EDB1-4F7A-81FC-6A54D0378656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2e6eb41e6ea95c3d0c759afdf930212864a893d","datavalue":{"value":{"entity-type":"item","numeric-id":1132885,"id":"Q1132885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$1A235BC5-EB13-4BBF-82C2-07916CBB774C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c3d461d813a1be0ca012b94d4687a47da49cb71","datavalue":{"value":{"entity-type":"item","numeric-id":1155633,"id":"Q1155633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$C9FAFDB9-2CA6-499E-8E6A-B635CFEBDA8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"727cbe0ca00c9bd3b90b6cc980c71b3e1f6b5dcf","datavalue":{"value":{"entity-type":"item","numeric-id":1213891,"id":"Q1213891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2200917$B6F7576F-19D8-47E8-B2CE-50C768846DBD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"42405c8600a0de92ee6b03f993f70b62d286d0c3","datavalue":{"value":"10.1016/J.JCTB.2020.05.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2200917$FB9A0166-B78E-499D-8C29-988FF1ED5C53","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8566d21de31ee9311f04420ae88104279c56799e","datavalue":{"value":{"entity-type":"item","numeric-id":2487986,"id":"Q2487986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f2df7411967db9b37892b17e79241498d0d2ff8","datavalue":{"value":{"amount":"+0.8968610167503357","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":"Q2200917$49D06014-118B-4E28-81FB-5889EC2609E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88c293250f07de72512aeeb9293faf663224fe31","datavalue":{"value":{"entity-type":"item","numeric-id":5284583,"id":"Q5284583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ea6595aade17dcf2eeb87a2c34a95d16209ea4c","datavalue":{"value":{"amount":"+0.8541831374168396","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":"Q2200917$86EABA8F-5060-46D6-BC03-66A0DC029046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64d9e7982ded48d7463032076bad05b1e54ceddf","datavalue":{"value":{"entity-type":"item","numeric-id":5405281,"id":"Q5405281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ea6595aade17dcf2eeb87a2c34a95d16209ea4c","datavalue":{"value":{"amount":"+0.8541831374168396","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":"Q2200917$E04E26D6-DA50-417E-9574-2FE45320A3D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d6b39984767126add425df3fabb43e58b92d273","datavalue":{"value":{"entity-type":"item","numeric-id":5463546,"id":"Q5463546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2f4aadc8d5e95a7d6953777a599577b19fab4c1","datavalue":{"value":{"amount":"+0.8478339910507202","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":"Q2200917$9DB759B1-420B-4462-9C7B-D4E328FAB19A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3207b87e87ca2c1d469c82b7fd647b71568876c8","datavalue":{"value":{"entity-type":"item","numeric-id":4020708,"id":"Q4020708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f407350a361ab00d36dd89758e795dd4afc419d0","datavalue":{"value":{"amount":"+0.8309786915779114","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":"Q2200917$7392145E-FFEA-4F04-8C54-4C9BE7D845E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2200917","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2200917"}}}}}