{"entities":{"Q1613435":{"pageid":1624175,"ns":120,"title":"Item:Q1613435","lastrevid":47977084,"modified":"2026-01-03T06:06:31Z","type":"item","id":"Q1613435","labels":{"en":{"language":"en","value":"The vertex-cover polynomial of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792372"}},"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":"Q1613435$D3D8044B-660D-426A-B31B-CC13B7AA2879","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8392bff4877af9ed2a2ebb7619ef3e76ff38de51","datavalue":{"value":{"text":"The vertex-cover polynomial of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613435$1AE4DF42-6451-40CE-9D5E-06A4A3595601","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"518a9d4453b8349f82e2166f74296cc10946a29c","datavalue":{"value":"1007.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613435$458804DD-E81E-4646-B0E1-6348B13C8C00","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"40fcef6e6c0f8d9fea63c8c29a15b6266e09900a","datavalue":{"value":"10.1016/S0012-365X(01)00272-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613435$5B31BB8D-7C3C-4FED-980B-2EB1F35D8B5A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613435$D2450A94-6D4E-4D21-9FD1-F64A1EAF404C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1613435$03B8AA1B-5963-4078-8AE1-66F7CC9883A3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d1f38e5da260a75e827857bb2a4bd03b1ce650e6","datavalue":{"value":"Let \\(G\\) be an undirected graph without multiple edges but possibly with loops. By an \\(r\\)-vertex cover in \\(G\\) we mean an \\(r\\)-element subset of the vertex set which has a common vertex with every edge in \\(G\\). Let \\(\\text{ cv}(G,r)\\) be the number of \\(r\\)-vertex covers in \\(G\\). The authors study properties of the generating function (called the vertex-cover polynomial) of the sequence of numbers of \\(r\\)-vertex covers , i.e. the function  \\[ \\Psi (G,\\tau)=\\sum_{r=0}^{v(G)}\\text{cv}(G,r){\\tau}^r. \\]  They show a recursive method of finding the vertex-cover polynomial for a given graph. Moreover, they compute the polynomial for several special classes of graphs. Finally, they show a relationship between their results and a problem in biological systematics.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613435$094204D6-2E12-43F5-8803-4C3D308B1BD4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2e24c05a8d3e4c23a551354bc6bd226b3d93e379","datavalue":{"value":{"entity-type":"item","numeric-id":298334,"id":"Q298334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613435$A4B8F4CF-C589-48C0-B4E2-7684FBF91741","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613435$38D55C65-1C8F-4EC8-B599-16C3434CAAA4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"db38a1824dd36a1f8c34b97fc4c7219deb16f133","datavalue":{"value":"1792372","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613435$8CE1D2A9-F90A-4901-B106-E294F699B2C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"33b1ae7074bb505cb2fd1273826dd5ba8ee3834d","datavalue":{"value":{"entity-type":"item","numeric-id":490408,"id":"Q490408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613435$F0182ED3-E943-4E60-9B61-EC3ACB7EAB64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b927b4f0b2432a7a29f0790af712f0b240c75f2","datavalue":{"value":{"entity-type":"item","numeric-id":1281781,"id":"Q1281781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613435$A51CE79E-8DC4-45AE-8634-61FFBB64AB2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2273a5d3af5295b897cafa89dd64aa90241e38b1","datavalue":{"value":{"entity-type":"item","numeric-id":1826957,"id":"Q1826957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613435$D82056A5-C5E2-42EA-81E8-35B314EE7335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1b9e588250376e4ef70df101e5a98aa9b927a039","datavalue":{"value":{"entity-type":"item","numeric-id":405202,"id":"Q405202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613435$C9059F8A-0CF6-468E-BA9E-F905D5AF65B4","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":"Q1613435$E9C2165F-1966-4B8E-B716-9E9A0BC1A0B5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"da3a5188dd78a630585b924919a6d727c97ec1fa","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(01)00272-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1613435$98D34023-0767-42C8-9E23-CF4470559788","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9db6a18a5a03b362ed331c781d888207adea861f","datavalue":{"value":"W2098003532","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613435$DD31C0F4-B0FA-4F5B-BE68-2F1A3FAB3F27","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01cf8162467dbc7864bb183b878e23fe6029919d","datavalue":{"value":{"entity-type":"item","numeric-id":2915793,"id":"Q2915793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76ae0b51b2bd5f0b403988b5b6238ac7fea5420e","datavalue":{"value":{"amount":"+0.8080278038978577","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":"Q1613435$FF63522D-A6D8-4CEA-987B-C9AEB84F1881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27bdebc915a7da263149330ffccbb71fd91b8221","datavalue":{"value":{"entity-type":"item","numeric-id":5069783,"id":"Q5069783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad9d27335757559f3118cc548ddfbc2b9d746645","datavalue":{"value":{"amount":"+0.7847722768783569","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":"Q1613435$28085B25-3DA3-4B52-BA2D-159938CF72F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cbb0009f05064d8fba64ba39eb9523172603c9d","datavalue":{"value":{"entity-type":"item","numeric-id":1907103,"id":"Q1907103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0841406da61a12ca51d5fe9f61d518457db4c71c","datavalue":{"value":{"amount":"+0.7806880474090576","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":"Q1613435$386328D6-BB39-4EC3-B9E4-3079200E8405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ec5718ef09a0f70850683464d15f5cd82ff706e","datavalue":{"value":{"entity-type":"item","numeric-id":4856276,"id":"Q4856276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f1f88e7b73ede3a2fcd63b0fe3de71f20134131","datavalue":{"value":{"amount":"+0.7789580821990967","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":"Q1613435$ADF5C13A-1873-4292-B63B-F79EB395BA64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72f3a3dd442cde52696d431bae39eee55ccb9d6c","datavalue":{"value":{"entity-type":"item","numeric-id":4601737,"id":"Q4601737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e693dc7c69a41251960b23c308f402b547a8d88","datavalue":{"value":{"amount":"+0.7621636390686035","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":"Q1613435$E0AD5FAA-8F1F-4A1A-89DD-8716F5B7EF98","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1613435","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1613435"}}}}}