{"entities":{"Q625376":{"pageid":627223,"ns":120,"title":"Item:Q625376","lastrevid":57107544,"modified":"2026-03-26T16:03:55Z","type":"item","id":"Q625376","labels":{"en":{"language":"en","value":"Counting connected set partitions of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5852464"}},"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":"Q625376$E398CB10-2D0F-451D-ACEB-D081B21E26D7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"db8c9f83f6032450a04f17ceee1974614142f39a","datavalue":{"value":{"text":"Counting connected set partitions of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q625376$57F24F4D-751C-465E-ACF4-7C2B2803694C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d6f908960d580d25c0b939124dd4a8be4d59e736","datavalue":{"value":"1209.05125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625376$1D06CFD9-9799-4DBE-A766-4D25F1148A0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c3c45e9636c6673f63f2309dc28061c3f44a68b3","datavalue":{"value":{"entity-type":"item","numeric-id":456394,"id":"Q456394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625376$9E24AD08-999C-473C-8A84-D02D2592EAFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c812610fcc0dd64cc524ad689f5de808633c3bfc","datavalue":{"value":{"entity-type":"item","numeric-id":426769,"id":"Q426769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625376$BC8D6323-1FEB-4713-9592-B7CAFD039C22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afe86b5abe805c5a9511d247ff75879dd089f0de","datavalue":{"value":{"entity-type":"item","numeric-id":343775,"id":"Q343775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625376$EBF7281A-6A2C-4407-BF84-F4FBF1DD7B21","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q625376$7BF2CE7A-6C8D-4DC1-8092-2F7D2F39C768","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"94e6b8b6646efe001edd9b80358ba7f0d8e6d8ae","datavalue":{"value":{"time":"+2011-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q625376$6E6A1363-A141-4A81-A48A-257CB9BDC609","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bbab1fdbf8471a20d97f48300c0e9866513c6d4a","datavalue":{"value":"https://arxiv.org/abs/1005.1726","type":"string"},"datatype":"url"},"type":"statement","id":"Q625376$FEC65CC2-6B9F-4BEE-90D8-3436F059C10A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"39ccaba619a76dade259696b37913ded16c7620d","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p14.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q625376$36784D86-F30A-4B04-9151-8FA202A5DD9F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"068a8882b037a85f8720831cb3d82941c6436e91","datavalue":{"value":"Summary: Let \\(G= (V,E)\\) be a simple undirected graph with \\(n\\) vertices then a set partition \\(\\pi= \\{V_1,\\dots, V_k\\}\\) of the vertex set of \\(G\\) is a connected set partition if each subgraph \\(G[V_j]\\) induced by the blocks \\(V_j\\) of \\(r\\) is connected for \\(1\\leq j\\leq k\\). Define \\(q_i(G)\\) as the number of connected set partitions in \\(G\\) with \\(i\\) blocks. The partition polynomial is \\(Q(G,x)= \\sum^n_{i=0} q_i(G)x^i\\). This paper presents a splitting approach to the partition polynomial on a separating vertex set \\(X\\) in \\(G\\) and summarizes some properties of the bond lattice. Furthermore the bivariate partition polynomial  \\[ Q(G,x,y)= \\sum^n_{i= 1} \\sum^m_{j=1} q_{ij}(G)x^iy^j \\]  is briefly discussed, where \\(q_{ij}(G)\\) counts the number of connected set partitions with \\(i\\) blocks and \\(j\\) intra block edges. Finally the complexity for the bivariate partition polynomial is proven to be \\(\\sharp P\\)-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q625376$CC76DDED-16C0-40CA-BBA4-7AE36D8FC50E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"26ba4f06ff5c7e92bd3a85f32aa625ae214ffe0f","datavalue":{"value":"05C31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625376$C7DDD85A-DA82-4A65-B768-3348729F89D5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b8ca775d8e4859062cb49e22af2481bc60d5e16a","datavalue":{"value":"5852464","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625376$109AD24C-FAF9-4F09-BA3D-2D7C61A4E373","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q625376$E718F11B-9103-4105-A48F-9FA630D2E22B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b79ccbad8715fa1fb5b6bed1880ca9805d35d983","datavalue":{"value":"bond lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q625376$284E3F24-2C7E-42FF-89CC-B386920DD549","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50940ff582f152d511fd3e73cca71bead0f1bf00","datavalue":{"value":"chromatic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q625376$A7434C09-9F69-48FC-9B75-C99D3335495A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2f6c7e8e4fb3b636d470109672ffc0467d736c0","datavalue":{"value":"splitting formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q625376$E6ABDB2D-A0F4-4E69-A054-85BF70926A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a28a4676dc8ecf6e3fc41856ca5c5d1516c182c","datavalue":{"value":"bounded tree-width, \\(\\sharp P\\)-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q625376$851A4E7E-C2F0-480D-A1CB-09CEFCB503E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e7a2d8375e8f45608549e9ce5d53adeb0d04567","datavalue":{"value":"partition polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q625376$4D55CDF9-8B51-4830-907A-5C915781E5B8","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":"Q625376$7EAA2E18-21E0-489E-8DE2-9C2BD3E51DFB","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"09dccb6fb37f0e4060992e9ff9e9f3f384f2820e","datavalue":{"value":"bafkreickihuwnoe4vsj2xbjzk5mto6yexsyeoywd2nr4oqfoezsd3sra4m","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q625376$F23CAA6C-639C-4E4B-97BE-E57EEAE96CEC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a48e81604c277ca406f5cc0fa54b465e7e026e4d","datavalue":{"value":{"entity-type":"item","numeric-id":4595189,"id":"Q4595189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e122d060e3012410b4444206164d46758b58d268","datavalue":{"value":{"amount":"+0.8351126909255981","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":"Q625376$29FD5A4E-9CC1-4009-AD3C-1AC35888DE92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22c8f5d0a465e1ab6c264abd4924ef477b4469a1","datavalue":{"value":{"entity-type":"item","numeric-id":2830375,"id":"Q2830375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79214abb6f93d493cd10f6a709ac849c3d235838","datavalue":{"value":{"amount":"+0.7933518290519714","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":"Q625376$B8A9D55E-FA36-4AB1-9B1C-F3962B807E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"020f63fd44b5a78e89d7cb78986512091d155f26","datavalue":{"value":{"entity-type":"item","numeric-id":1057062,"id":"Q1057062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32d908a240c3304930e5474b04feec9c666a75a3","datavalue":{"value":{"amount":"+0.7747468948364258","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":"Q625376$AB980E43-40D4-4769-9B39-BFCB6F8A2932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64c1a2f594656a73d6372399e7c925d488c0571d","datavalue":{"value":{"entity-type":"item","numeric-id":3472142,"id":"Q3472142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"206c96759289e2b5a9b450b9bba14cd7b2e23296","datavalue":{"value":{"amount":"+0.7653990387916565","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":"Q625376$A86ADC6B-E7EF-4FF1-B6A1-E69E5B8934BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c9ff6f68d29865d3d49ddf6af9b436b499ca1bf","datavalue":{"value":{"entity-type":"item","numeric-id":1773211,"id":"Q1773211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7174116739fb96a3cff986fa437148327c15420c","datavalue":{"value":{"amount":"+0.763602614402771","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":"Q625376$FB1608F0-EC40-4808-B34B-CCBAB209FA00","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:625376","badges":[]}}}}}