{"entities":{"Q854836":{"pageid":856684,"ns":120,"title":"Item:Q854836","lastrevid":64912449,"modified":"2026-04-11T23:03:50Z","type":"item","id":"Q854836","labels":{"en":{"language":"en","value":"On the dependence polynomial of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5077711"}},"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":"Q854836$9F84CC7B-6B98-4277-85CC-0C6545B0633E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f9dec6e8c65956f7f3fdbf1eed5456defc7cb137","datavalue":{"value":{"text":"On the dependence polynomial of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q854836$A425C59F-2EFE-4A2D-9380-AFBE4AB6451A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"58af762606c630467ed5c9e5edf0e4815088738a","datavalue":{"value":"1110.05036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q854836$64DA4549-3C0C-4835-900D-09938263223D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7931b65763ce60aa07ef069f7e649b4311b65a5d","datavalue":{"value":{"entity-type":"item","numeric-id":328218,"id":"Q328218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$149056FA-98F8-4C05-9CB0-70C64766B8D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"427ad81cb678607c612fd0279eec65c495fd1865","datavalue":{"value":{"entity-type":"item","numeric-id":1734960,"id":"Q1734960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$FB24093C-6A05-4E6B-AFCF-FDB84C3B978C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5cdbbc38bd0212cc8cc5d194d063f74d66b1ae7","datavalue":{"value":{"entity-type":"item","numeric-id":165832,"id":"Q165832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$665684A8-E872-4FD5-B31E-03A33171AD58","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$F3602851-FC93-4C7A-A1F9-AE3E32FCF17B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f69fd7e33e5959021461630cbc83478a74a6768f","datavalue":{"value":{"time":"+2006-12-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q854836$6828B68D-7B4B-4BB2-9679-30679B643DD5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"634424dc4f9b0bf333f92dfbfa74718c5db9cfae","datavalue":{"value":"For an \\(n\\)-vertex graph \\(G\\) and \\(i=0, 1, \\dots, n\\), let \\(c_i\\) denote the number of complete subgraphs on \\(i\\) vertices in \\(G\\). The dependence polynomial \\(P_G(z)\\) of \\(G\\) is defined by \\(P_G(z)=1+\\sum_{i=1}^n (-1)^i c_iz^i\\). Using a M\u00f6bius-type inversion formula, the authors show that   \\[ \\begin{aligned} P_G(z)&=\\sum_{\\emptyset\\not=\\mathcal{W}\\subseteq\\mathcal{V}} (-1)^{| \\mathcal{W}| -1}(1-z)^{| \\bigcap\\mathcal{W}| }\\\\ &=\\sum_{k=1}^m (-1)^{k-1} \\sum_{1\\leq i_1 <\\cdots < i_k\\leq m} (1-z)^{| V_{i_1}\\cap\\cdots\\cap V_{i_k}| },\\end{aligned} \\]   where \\(\\mathcal{V}=\\{V_1, \\dots, V_m\\}\\) denotes the set of (distinct) maximal complete subgraphs of \\(G\\). For the line graph \\(L(G)\\) of \\(G=(V,E)\\), this reads as follows: \\(P_{L(G)}(z)=\\sum_{v\\in V}(1-z)^{d(v)} - tz^3+ez+1-n\\), where \\(n=| V| \\), \\(e=| E| \\), \\(t\\) denotes the number of triangles in \\(G\\), and \\(d(v)\\) is the degree of \\(v\\) in \\(G\\). The authors also discuss the relation of the dependence polynomial of the complement of the line graph of \\(G\\) to the matching polynomial of \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q854836$07A9AAAA-A429-4BCB-8E4A-C1DF53C07067","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$465960F2-40C0-47F3-BBCF-9BB2C3B6D7D7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q854836$8A2C8CF9-C732-439D-BD75-78C2AAF3F850","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"018c102416b80c0d27374415e9126ec8f3acd043","datavalue":{"value":"5077711","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q854836$1AF7F7F9-E0D4-4D2E-843B-C5DEFCBA81B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42bbacba9e0754a3d3cb974ea2438ef2b76237bb","datavalue":{"value":"clique polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q854836$FD9D80FD-9B9D-434A-A610-9279ADF4F155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfb8845d06bb84172e773d3c2830dce553ba7843","datavalue":{"value":"matching polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q854836$9FFC4CEC-1B95-4E7F-B97B-8AE509D68074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34783be7cb07be74f453b9d5a8761bddb5dcf0b1","datavalue":{"value":"line graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q854836$C275BDA2-7502-40B5-A498-93C4ABFF2328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"020dcd602d93acb62a2ccabd471119c076b75e9d","datavalue":{"value":"M\u00f6bius inversion","type":"string"},"datatype":"string"},"type":"statement","id":"Q854836$CD656F8F-37B1-4062-8747-4FBF0BDFF6F9","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":"Q854836$441A4529-0948-4C0C-A873-14EDAAEC548A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0d9bc18c729fea387f51be18fd88052eda3a394a","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2005.07.015","type":"string"},"datatype":"url"},"type":"statement","id":"Q854836$212263C5-50D9-410A-8D53-1DDD40FE3F6C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fb98dacd382b068c4de8192b1b556eac29f5c484","datavalue":{"value":"W2089276257","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q854836$8E11DF5A-9868-4FC4-B096-0F34F45C507B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8d8f7eed5395c1964bfb942c2b38d0ba78d325b","datavalue":{"value":{"entity-type":"item","numeric-id":2716005,"id":"Q2716005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$8B74DD23-F3B5-440F-8E5A-922DAF10A8AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da9a4c59ddb0bb6f8e8e4b091fa1c53294557744","datavalue":{"value":{"entity-type":"item","numeric-id":1322274,"id":"Q1322274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$C1A16308-DF34-4BB8-B5ED-0781BE1DD316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"707bf809d4c171a39b9f44a814f02c129abd1726","datavalue":{"value":{"entity-type":"item","numeric-id":2640617,"id":"Q2640617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$3283B7CD-E763-4D64-AA43-46CDEB31F188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cab96db3f55928700487786eca89bec7ad9d7c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3137758,"id":"Q3137758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$3A36BA11-7A31-4421-B5C2-D06E4DE96590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c75c718a2a5e74afba5cee748dd4aad18f193edd","datavalue":{"value":{"entity-type":"item","numeric-id":294815,"id":"Q294815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$4F9E48D6-A251-4614-96B8-C963B235E994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$13BD82AF-A52E-401B-9788-0E919815312E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c42b17a9e65624167c0afafce75cee382a5dd7e5","datavalue":{"value":{"entity-type":"item","numeric-id":5731810,"id":"Q5731810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q854836$08586DDD-DCB2-4185-A476-9532A14DFF88","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4ee7ee08775604d7acd3b9a054ac855867be7811","datavalue":{"value":"10.1016/J.EJC.2005.07.015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q854836$0758440F-7B99-462C-ABCD-4AC6E047200F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1eaa7aecb6693158a867b68d6999dfbec3dc5cbc","datavalue":{"value":{"entity-type":"item","numeric-id":2640617,"id":"Q2640617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88de9e5a712a9503cf93d8c644b23d9ed7bfef4f","datavalue":{"value":{"amount":"+0.8491220474243164","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":"Q854836$DF989D82-4D40-40FC-831A-879A449BC3C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19497d84215d6e7191399b23eff0e62b4566f999","datavalue":{"value":{"entity-type":"item","numeric-id":895839,"id":"Q895839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a36a6ae6945d72d1b39857b0746960dfbf603b4","datavalue":{"value":{"amount":"+0.8331791162490845","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":"Q854836$41E66C2A-B78F-424D-B849-F899F4402B3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22f35a4a6c03a546e3e06209f48671461a78ee0b","datavalue":{"value":{"entity-type":"item","numeric-id":5284028,"id":"Q5284028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"458b06cda149be0cd0606c38773b96a19de250f5","datavalue":{"value":{"amount":"+0.7517807483673096","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":"Q854836$9A63C28E-8CE4-4D49-A3A6-D27FE37564D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e20993c8ad2296bbd2ed6f86255b8a40da75222","datavalue":{"value":{"entity-type":"item","numeric-id":1322274,"id":"Q1322274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"458b06cda149be0cd0606c38773b96a19de250f5","datavalue":{"value":{"amount":"+0.7517807483673096","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":"Q854836$C4270A51-99C2-44FD-B2F1-5368708B186A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"952f9ad3896e79db9e2be57c2d1111334665965d","datavalue":{"value":{"entity-type":"item","numeric-id":5461436,"id":"Q5461436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"059730e59ff761149e34f6bc530a1f28a68008c1","datavalue":{"value":{"amount":"+0.7384951710700989","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":"Q854836$8BBDB853-F503-461A-BD62-7C592269D276","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the dependence polynomial of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_dependence_polynomial_of_a_graph"}}}}}