{"entities":{"Q640424":{"pageid":642272,"ns":120,"title":"Item:Q640424","lastrevid":63215706,"modified":"2026-04-11T11:23:32Z","type":"item","id":"Q640424","labels":{"en":{"language":"en","value":"Extremal problems for independent set enumeration"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5960031"}},"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":"Q640424$B0DF2E3A-262D-4BD8-B834-EFC24E6E708E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ec178f89cf599a795a39dd0a0c6968f095787260","datavalue":{"value":{"text":"Extremal problems for independent set enumeration","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q640424$60D46DEB-515C-49AC-BBD8-BED31F4F62D6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"46b0c47034aeb7b6da20738a178b48db4578e06c","datavalue":{"value":"1229.05138","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640424$5406E7D4-DA2B-40B5-A467-701B1A38C485","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab5a422918621b46149cf3b2991e66a46628e6cf","datavalue":{"value":{"entity-type":"item","numeric-id":271642,"id":"Q271642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640424$1F719029-1453-449A-8C61-A2E3A91F6DFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c7b5ae0db868a569f1e85ca0ccc358e9e294f698","datavalue":{"value":{"entity-type":"item","numeric-id":456298,"id":"Q456298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640424$83A88853-C9D3-48D6-89EB-3E244875472E","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":"Q640424$1D5C4857-369E-4791-A539-2DEAD813BBF8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9767fe8dd1d6f9791ae763e9a67550b5f9aa27e1","datavalue":{"value":{"time":"+2011-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q640424$8732DE70-D502-4200-B087-0CD979B3EF1D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ed452043676ae49524715dd0f201b77af7c757d0","datavalue":{"value":"https://eudml.org/doc/223259","type":"string"},"datatype":"url"},"type":"statement","id":"Q640424$72BE8B93-B110-40F6-950D-9747018A052B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5e9eb75e75a1aa3ab9fc2f5d686fb34c30762a6e","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p169.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q640424$44337BBF-7C7D-4C93-ABF8-8CD59578A466","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1f828cbd82b89db6788af876e2f173ab0d64ef25","datavalue":{"value":"Summary: The study of the number of independent sets in a graph has a rich history. Recently, Kahn proved that disjoint unions of \\(K_{r,r}\\)'s have the maximum number of independent sets amongst \\(r\\)-regular bipartite graphs. Zhao extended this to all \\(r\\)-regular graphs. If we instead restrict the class of graphs to those on a fixed number of vertices and edges, then the Kruskal-Katona theorem implies that the graph with the maximum number of independent sets is the lex graph, where edges form an initial segment of the lexicographic ordering.    In this paper, we study three related questions. Firstly, we prove that the lex graph has the maximum number of weighted independent sets for any appropriate weighting. Secondly, we solve the problem of maximizing the number of independents sets in graphs with specified independence number or clique number. Finally, for \\(m \\leq n\\), we find the graphs with the minimum number of independent sets for graphs with \\(n\\) vertices and \\(m\\) edges.","type":"string"},"datatype":"string"},"type":"statement","id":"Q640424$A3B07343-9235-4F45-82FE-15695FF5A36B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640424$55ADE078-E41D-4CBC-AF5C-31DA0CA15FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640424$62082759-B3CF-4E15-95DD-F1B10BEB2043","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a31a0a41fbe8cc0744ee578ba91406d207887768","datavalue":{"value":"5960031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640424$843EE7F8-CFC7-487B-87BE-08611E723173","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"733772e97530a8d4d58c0a4720cc77d93e35db47","datavalue":{"value":"lex graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q640424$A09D41D3-8148-4BC7-816C-62F42F320063","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":"Q640424$E9213A11-B324-4E4A-9B8C-2DDE68CC4301","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"4683d880c8aeb8cfbebeaef2382ee5d9810d25f6","datavalue":{"value":"bafkreiefcbvcw7vl2ykgizxqpiu5fkbpypebbei4ucpvtrvjqwdvbix7vu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640424$FE3AD7D4-1170-435E-97E0-4AB8049F153A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5586d61dda28bc4412940d455e27cce0242dbd9e","datavalue":{"value":{"entity-type":"item","numeric-id":3557538,"id":"Q3557538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b140e1686809281774e4c4a6748e82061509d537","datavalue":{"value":{"amount":"+0.840631902217865","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":"Q640424$13D157F5-C555-45B0-839D-99A177F00587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a23c573689c04115c99ae644b7d13cc2265476b","datavalue":{"value":{"entity-type":"item","numeric-id":456377,"id":"Q456377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c7bad3169a2efdf9b8f2145356ec7c1b50cad48","datavalue":{"value":{"amount":"+0.8265216946601868","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":"Q640424$534F02AF-F193-4017-A8B4-583CAAE7DF57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7b30552234855aa0fdb65eaa300ce2114f73e58","datavalue":{"value":{"entity-type":"item","numeric-id":4575432,"id":"Q4575432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca7db109207875d8b289a3ee93519c6683a745c7","datavalue":{"value":{"amount":"+0.8069023489952087","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":"Q640424$36A69B4D-8E4C-4AC3-B1F6-69AE3F0F78A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67009b1d64ac32e561c72f293a1076354a047b01","datavalue":{"value":{"entity-type":"item","numeric-id":4660722,"id":"Q4660722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a665403a43f789a61dc793da033036d2ed285ca9","datavalue":{"value":{"amount":"+0.8056423664093018","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":"Q640424$8BEC5775-61DA-47C4-9256-97CA9BDEB370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"426a69a8ce61c44bb4bfd8b295995a2eba4a69bc","datavalue":{"value":{"entity-type":"item","numeric-id":2312617,"id":"Q2312617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16d3234168245c8c540664d5eed74aea2575033b","datavalue":{"value":{"amount":"+0.8013813495635986","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":"Q640424$50109AD8-7106-45E1-9AC8-B4D2772C89B5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Extremal problems for independent set enumeration","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Extremal_problems_for_independent_set_enumeration"}}}}}