{"entities":{"Q456377":{"pageid":458144,"ns":120,"title":"Item:Q456377","lastrevid":42501010,"modified":"2025-06-30T14:39:43Z","type":"item","id":"Q456377","labels":{"en":{"language":"en","value":"Independent sets in graphs with given minimum degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6098379"}},"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":"Q456377$05ED09D3-EA49-420B-8309-EB28E4B31C65","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d1c75635c26011867dc7d8078631711774b4227","datavalue":{"value":{"text":"Independent sets in graphs with given minimum degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q456377$468D00A4-BE96-426C-BDD4-F45B8FCE4E48","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5c3c3f148962307862f82296de98489102995526","datavalue":{"value":"1252.05157","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456377$F47728D8-D59A-44CB-B896-BA922EA5D897","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"51e628389b42fba01853cb1d3130441c7e1e1b3c","datavalue":{"value":{"entity-type":"item","numeric-id":456375,"id":"Q456375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456377$C75CB7EC-7F6D-4298-B74B-18AC19A76D73","rank":"normal"},{"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":"Q456377$08307558-8368-4D5C-90C5-76BD5980969C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a734b09f8bcc20e4cc822b6cd103f223d0aa17b8","datavalue":{"value":{"entity-type":"item","numeric-id":456376,"id":"Q456376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456377$8F3D6C06-C214-452B-A867-F0716C228F52","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":"Q456377$314CD9F8-3FB1-4F39-BBAD-46CF4C3D4F9A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6ee92d50481ed05c06549abf63f6ece88b90dd74","datavalue":{"value":{"time":"+2012-10-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":"Q456377$CA127B40-053D-4EC1-98A7-E3BB7AE23638","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"46f449027585acf28ab21439548ef6f2cadcfeec","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p37","type":"string"},"datatype":"url"},"type":"statement","id":"Q456377$83C2FBC0-C5C7-431D-B090-B7FB04CBA3BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"46226e6d3b21b00f4ae429178aadd537dba83fe6","datavalue":{"value":"Summary: The enumeration of independent sets in graphs with various restrictions has been a topic of much interest of late. Let \\(i(G)\\) be the number of independent sets in a graph \\(G\\) and let \\(i_t(G)\\) be the number of independent sets in \\(G\\) of size \\(t\\). Kahn used entropy to show that if \\(G\\) is an \\(r\\)-regular bipartite graph with \\(n\\) vertices, then \\(i(G)\\leq i(K_{r,r})^{n/2r}\\). Zhao used bipartite double covers to extend this bound to general \\(r\\)-regular graphs. \\textit{D. Galvin} [Discrete Math. 311, No. 20, 2105--2112 (2011; Zbl 1228.05228)] proved that if \\(G\\) is a graph with \\(\\delta(G)\\geq \\delta\\) and \\(n\\) large enough, then \\(i(G)\\leq i(K_{\\delta,n-\\delta})\\).    In this paper, we prove that if \\(G\\) is a bipartite graph on \\(n\\) vertices with \\(\\delta(G)\\geq\\delta\\) where \\(n\\geq 2\\delta\\), then \\(i_t(G)\\leq i_t(K_{\\delta,n-\\delta})\\) when \\(t\\geq 3\\). We note that this result cannot be extended to \\(t=2\\) (and is trivial for \\(t=0,1)\\). Also, we use Kahn's entropy argument and Zhao's extension to prove that if \\(G\\) is a graph with \\(n\\) vertices, \\(\\delta(G)\\geq\\delta\\), and \\(\\Delta(G)\\leq \\Delta\\), then \\(i(G)\\leq i(K_{\\delta,\\Delta})^{n/2\\delta}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q456377$591970E4-3FC4-4592-BEF4-A6323D6B3C40","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456377$658A5F09-8C00-46EE-B7D5-FDB6D2070F03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456377$1358DB1A-7ED5-4A6C-82CA-22ABDAC052B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456377$13D67027-C667-405E-B979-E7ADB2EAFCD5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6bf3e92579ba5b8409c95d2aac46255be0202fb3","datavalue":{"value":"6098379","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456377$09E92AFF-3EDF-4D9A-9B13-CD3DE4565835","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da98424ce33577d45b7fc15fa7bb12b966b80d69","datavalue":{"value":"independent set enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q456377$1CBBE95F-713C-4C6B-B7EA-F4E542F5429B","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":"Q456377$9271AB4A-60C5-4A76-A8D8-DCFF3E481B97","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"8944e700cee6e1bf13621dedb1102185f4388e40","datavalue":{"value":"bafkreifxcynzrjjirc4npelelecbyho2xon4wzk3ukmi2w6xy6rayiq7xe","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456377$7658FFCA-F71C-43AD-BC9C-4C2252589C60","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2ec4d1542b2e1725b3310997e282147ea021203","datavalue":{"value":{"entity-type":"item","numeric-id":5397737,"id":"Q5397737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73de09d1edd05bb8ce61bf0ab32d895d408b6cbe","datavalue":{"value":{"amount":"+0.9899035","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$E0C3A744-1C28-408A-AF1D-2A4B3CCBAEE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce965b790af0a8829c5d1471dd7165892157f8b3","datavalue":{"value":{"entity-type":"item","numeric-id":501998,"id":"Q501998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdca56e49383759a3f5288d2fdc4857397d61591","datavalue":{"value":{"amount":"+0.94252104","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$4FEEF20E-AF18-490E-B67B-F1DDB3A5D96D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0a2479f3797733cdd70a3538446ae6cb16246cc","datavalue":{"value":{"entity-type":"item","numeric-id":1182974,"id":"Q1182974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f2e3323237a7c115bbad9d2ed3942f99eb1020b","datavalue":{"value":{"amount":"+0.941952","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$2D87B2A3-3530-425C-A8A6-63015730FEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee143cba28e25a6be42713e2ee43097dc3a8be07","datavalue":{"value":{"entity-type":"item","numeric-id":659691,"id":"Q659691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16d7062227072a3701471e79e8a1bf5f3a21c390","datavalue":{"value":{"amount":"+0.9346806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$93BA1621-9F79-4BA2-BBD1-E8EF4F307145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"955aee3ab14833c1132944179d36c4724ef42a0d","datavalue":{"value":{"entity-type":"item","numeric-id":2934676,"id":"Q2934676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74cd188a8f574aa2801d7fa36681c05e63d5203f","datavalue":{"value":{"amount":"+0.9339267","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$B285EC6F-9F8D-45A6-8EFE-89AE4CA1D0DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44268bb97c88ee0a51a9ef0fec672913b8848980","datavalue":{"value":{"entity-type":"item","numeric-id":5418775,"id":"Q5418775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a7c12b2fccfadc8cb67ca795023f45472ae1f8e","datavalue":{"value":{"amount":"+0.9321259","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$A16B4983-D06F-439F-9540-1936605A24B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a181986d63478ae5ca1253f0d5afadbc20592641","datavalue":{"value":{"entity-type":"item","numeric-id":5387693,"id":"Q5387693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa4bbf667c36710e48ff46a10ca986d76fa238a6","datavalue":{"value":{"amount":"+0.93034893","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$A2502B96-0547-4958-98A8-A33C6D106896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfab269f984987bbd2615e90a92759fdfedb6d19","datavalue":{"value":{"entity-type":"item","numeric-id":5193023,"id":"Q5193023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d268be38f97d0e37100b7cbf0b15be3f847c2d5e","datavalue":{"value":{"amount":"+0.9277401","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$B446D79C-C09A-4CE7-861D-115E80F801FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e097e1a7d9ea437752cf7a784884d09ddfb8f6a","datavalue":{"value":{"entity-type":"item","numeric-id":3220625,"id":"Q3220625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27b56a935e4df21781d7938d9e089daf603b4492","datavalue":{"value":{"amount":"+0.92518926","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$6C5A6EE5-DA08-48C2-8A27-1D7C0472DCFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a34af50130c7a399c5353a001dab0acf28ef2ef4","datavalue":{"value":{"entity-type":"item","numeric-id":2876034,"id":"Q2876034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9610a1e10cbe1fc2a3ece07d40574466ef180ebf","datavalue":{"value":{"amount":"+0.9246891","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q456377$F9CBBDC1-D99C-4D05-A65B-128A96A8E6EE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:456377","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:456377"}}}}}