{"entities":{"Q426841":{"pageid":428608,"ns":120,"title":"Item:Q426841","lastrevid":61796478,"modified":"2026-04-11T01:42:59Z","type":"item","id":"Q426841","labels":{"en":{"language":"en","value":"Largest and smallest minimal percolating sets in trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6045688"}},"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":"Q426841$1EFB6947-9388-4B07-A038-FB4198215749","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2bda631d22bb277bf18c116720ab935481672470","datavalue":{"value":{"text":"Largest and smallest minimal percolating sets in trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q426841$2EF3B21E-3A8D-4CF3-8861-328399AA887B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"82de757b60d2813e86b989bc3b9b2cb1ae594254","datavalue":{"value":"1244.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426841$D67E8C77-41A1-4087-B0BB-A249D38E6140","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2af918200bdc976f6c5f14feaa7a3d4800576919","datavalue":{"value":{"entity-type":"item","numeric-id":426840,"id":"Q426840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426841$B7A61934-3884-4ADB-88BB-8C987C36068B","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":"Q426841$DB94E017-1BA9-40A5-89D9-D4E59B0D0D13","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4bc8e8f32e3771ea3dc331f4cf4795267b160813","datavalue":{"value":{"time":"+2012-06-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q426841$DD8D5DB7-5EAF-4883-A56A-359DE3BA7C48","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3d5ab529e339a807628aba219d1c6b8ae72d2b60","datavalue":{"value":"http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i1p64","type":"string"},"datatype":"url"},"type":"statement","id":"Q426841$24A553C9-393D-4486-844A-C475E8EE46BA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b05fec9ea95ae16d3e95ba827c0603be7f6d272e","datavalue":{"value":"Summary: Originally introduced by \\textit{J. Chalupa}, \\textit{P.L. Leath} and \\textit{G.R. Reich} [``Bootstrap percolation on a Bethe lattice'', J. Phys. C., 12, L31--L35, (1979)] for use in modeling disordered magnetic systems, \\(r\\)-bootstrap percolation is the following deterministic process on a graph. Given an initial infected set, vertices with at least \\(r\\) infected neighbors are infected until no new vertices can be infected. A set percolates if it infects all the vertices of the graph, and a percolating set is minimal if no proper subset percolates. We consider minimal percolating sets in finite trees.    We show that if \\(A\\) is a minimal percolating set on a tree \\(T\\) with \\(n\\) vertices and \\(\\ell\\) vertices of degree less than \\(r\\) (leaves in the case \\(r=2\\)), then \\(\\frac{(r-1)n+1}{r} \\leq |A| \\leq \\frac{rn+\\ell}{r+1}\\). Moreover, we show that the difference between the sizes of a largest and smallest minimal percolating sets is at most \\(\\frac{(r-1)(n-1)}{r^2}\\). Finally, we describe \\(O(n)\\) algorithms for computing the largest (for \\(r=2\\)) and smallest (for \\(r \\geq 2\\)) minimal percolating sets.","type":"string"},"datatype":"string"},"type":"statement","id":"Q426841$A3874D16-0D57-43DC-BA3F-B3F52771E0A1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426841$D2A65D62-DAA9-4699-AADE-27743206A4DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426841$E72926D0-20D3-411C-B268-D35DBDF77021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426841$FC332A31-1B83-4CA8-8B5A-54F452773874","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4cfed5ae004c756c92dbcacd596f439e762bc32d","datavalue":{"value":"6045688","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426841$E0821151-57A1-44D5-9447-BB7E8700C104","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"539be726cb8dfa54cd0c12914c99488c7ea42ea5","datavalue":{"value":"percolation","type":"string"},"datatype":"string"},"type":"statement","id":"Q426841$68E7466B-B929-44BD-8E84-D80763714DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q426841$2FB341EC-048D-4066-AE4A-43ABCF3DBF5F","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":"Q426841$02DC7D6D-9C89-480C-87D9-B11730720360","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"bdeda60996b96c33bea985bf10c1157c8346c371","datavalue":{"value":"bafkreic6pd3l34urdie667b5pwubnz5anvgmutnrx76e3ky5l6kurcvpcu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426841$662509D6-DBE2-45E2-A37D-0A4A754A1E83","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4cdbc8cb549992d038a8dd8ed70b83e55bace63","datavalue":{"value":{"entity-type":"item","numeric-id":5045263,"id":"Q5045263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d2589590747d49f9ddf073185c01792eb7cb651","datavalue":{"value":{"amount":"+0.8412058353424072","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":"Q426841$8B8AD154-9B8D-47A2-9F57-7A80F1BD01B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4065408a835e4c1c71ac7174d1916db560132e6a","datavalue":{"value":{"entity-type":"item","numeric-id":2185227,"id":"Q2185227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07dfbbf5042a568355eb8a0d5696dd2971b18ab5","datavalue":{"value":{"amount":"+0.83404141664505","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":"Q426841$8E52B6C3-03C4-4DE5-9984-95D7383A88E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0d8c14f5d3521f9d15f2b0bf5bb469d7a7dde5d","datavalue":{"value":{"entity-type":"item","numeric-id":976739,"id":"Q976739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdfa92d95d31be2fe8336611c601d7733c4bfef8","datavalue":{"value":{"amount":"+0.8313132524490356","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":"Q426841$1092EFC2-741B-4ED1-AD04-075EECC858B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97d24ffcaaecdf6c00fb670878031de8616cf28b","datavalue":{"value":{"entity-type":"item","numeric-id":1010903,"id":"Q1010903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ba336bb1513d1d6b86b19f40750bd567c430ccc","datavalue":{"value":{"amount":"+0.829953670501709","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":"Q426841$B37CA55B-9191-4821-9412-8B676084A480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dbbeb31dce5f7b97ac72aac5244f3ffc283b827","datavalue":{"value":{"entity-type":"item","numeric-id":396751,"id":"Q396751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2031fe1bd7893c15cf0216918c5096d8e1a860ca","datavalue":{"value":{"amount":"+0.7944531440734863","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":"Q426841$3544B0E9-01CA-41CB-84DC-0CF8E9286A95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Largest and smallest minimal percolating sets in trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Largest_and_smallest_minimal_percolating_sets_in_trees"}}}}}