{"entities":{"Q659685":{"pageid":661534,"ns":120,"title":"Item:Q659685","lastrevid":63397122,"modified":"2026-04-11T12:37:30Z","type":"item","id":"Q659685","labels":{"en":{"language":"en","value":"Cleaning with brooms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5999825"}},"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":"Q659685$F33C2D14-D4A6-4D8C-A3FE-36543873AD78","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3c24f28c07de1079bada848ec81afdf9a36f4922","datavalue":{"value":{"text":"Cleaning with brooms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q659685$F1496181-8097-4279-B550-5A7766EEA47D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"be728e959f638626e9f5e1f2d3e10a62c9f0bbfa","datavalue":{"value":"1235.05094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659685$705B1045-1DEF-43FD-8D03-775882E961DC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"099da98a3a1b5ade622c3974c3a9827efb7b08a7","datavalue":{"value":{"entity-type":"item","numeric-id":244922,"id":"Q244922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$99839B85-B20B-4441-860B-A362C40AD687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5676fa5282611dbd0fab8edb7a4f82cf8ae7a025","datavalue":{"value":{"entity-type":"item","numeric-id":215016,"id":"Q215016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$6D13C59E-9A3D-4905-B0BF-D21CE26CA24C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6197eba997efc9b4d1afb25ce947d80519065cc","datavalue":{"value":{"entity-type":"item","numeric-id":265089,"id":"Q265089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$A5AD321A-CFF5-4A4D-985D-52F9AF50B0B2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$A2D27D6D-11F0-4195-AD71-10013B3A99DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a8ae18c3aa8afb0a38e8de58d984f857c905ff39","datavalue":{"value":{"time":"+2012-01-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":"Q659685$8B7F9FA7-7335-4864-AEE5-0ED37BE912D2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8d051941244c545e06fed2b0b910b454a167f5a","datavalue":{"value":"Cleaning with brushes is a game on graphs that was introduced by the authors in [``Cleaning a network with brushes,'' Theor.\\ Comput.\\ Sci.\\ 399, 191--205 (2008; Zbl 1187.68185)]. It is described in the review of a paper by \\textit{N. Alon}, \\textit{P. Praat}, and \\textit{N. Wormald} [``Cleaning regular graphs with brushes,'' SIAM J.\\ Discrete Math.\\ 23, No.\\,1, 233--250 (2008; Zbl 1187.05066)]. Cleaning with brooms refers to the same game. While the brush number \\(b(G)\\) is the minimum number of brushes needed to clean the graph \\(G\\), the broom number \\(B(G)\\) is the maximum number of brushes that can be used to clean \\(G\\). The paper gives various bounds on \\(B(G)\\), such as \\(B(G) \\leq |E|\\) or \\(B(G) \\leq \\lfloor|V|^2/4\\rfloor\\) for all graphs \\(G=(V,E)\\). The former bound is attained if and only if \\(G\\) is bipartite, and the latter bound is attained for complete graphs \\(G\\). For a graph \\(G+e\\), obtained from \\(G\\) by adding one edge, \\(B(G) \\leq B(G+e) \\leq B(G)+1\\) holds. We have \\(b(G) = B(G)\\) if and only if \\(G\\) is a disjoint union of complete graphs. Further bounds on \\(B(G)\\) are shown for the cartesian product of complete graphs and the strong product of cycles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q659685$695C7C31-A2BC-4FC0-86BE-96CA41D17E1C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659685$C2645BBC-DB60-46D4-B5EC-D30F03AB92CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659685$74D3E4AE-3785-46C6-81DB-75BB9E6513AB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2fc69ac72204746bd551e5a32509f6eff089e79d","datavalue":{"value":"5999825","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659685$05AD85FB-38E9-49FC-A631-4A807C6DA542","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f937dca815a0b04b62b1f80953688fecccc223df","datavalue":{"value":"graph cleaning","type":"string"},"datatype":"string"},"type":"statement","id":"Q659685$FE3BFE87-74BA-4686-AFC7-C42688120796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b322c03f72bfbe9e7516683225803e7e94a5704f","datavalue":{"value":"graph searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q659685$20E18E12-67F7-491D-A988-DBF28BCD3DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c87177b41f54dbc1badaa2704588905fad2812f2","datavalue":{"value":"chip-firing game","type":"string"},"datatype":"string"},"type":"statement","id":"Q659685$DB7A3184-5AD9-497B-876C-D7EA6D890E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d0bfef4fe379fb8ab337075f6458f03defdcf24","datavalue":{"value":"broom number","type":"string"},"datatype":"string"},"type":"statement","id":"Q659685$05F81E7F-5628-4F01-AFA8-E89F522BFE59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a986bb5c4e73945b0bbaeafbcd75045929989e1","datavalue":{"value":"brush number","type":"string"},"datatype":"string"},"type":"statement","id":"Q659685$25404DAC-DAD1-495B-8FB6-C9E764617FD7","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":"Q659685$C93F5C90-9B0B-4CAE-8E89-24E73E24BB80","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c52838074c836fd6ae761622a9498afd918273dc","datavalue":{"value":"https://doi.org/10.1007/s00373-010-0965-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q659685$29BD5FD7-2840-4307-8DC6-53532D705701","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"33116b8abf86ea691f53675afa2bd5199fbf0e3c","datavalue":{"value":"W2091551894","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659685$7DB939C6-3BB2-4776-BCCB-D795B296DAB6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4e03ac707083102d3819ef104a31be58e564748","datavalue":{"value":{"entity-type":"item","numeric-id":5189512,"id":"Q5189512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$713CF16A-84EA-4721-A7DC-04699800953B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9449871618984664aec5fee2e3ba7c11770dd57","datavalue":{"value":{"entity-type":"item","numeric-id":1775059,"id":"Q1775059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$459A4941-563F-4B3F-8DC2-89A5064965BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"254786e02bb0dde53c0aa483c883dcf5bff6ff68","datavalue":{"value":{"entity-type":"item","numeric-id":987793,"id":"Q987793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$40CCB132-49B3-440B-A954-2E5F00B101D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bd1acecce4cd634b2848e5ebbfe1b75a0d9aef1","datavalue":{"value":{"entity-type":"item","numeric-id":968165,"id":"Q968165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$3B55A48E-85D7-4ABC-AAB3-988D161E2CD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2a51201cfc08399524fa098435c70eb3f20cf05","datavalue":{"value":{"entity-type":"item","numeric-id":5387696,"id":"Q5387696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$EE2697E0-0D21-4C29-A0BD-A7676DAF57A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c32cb94ae4b300f1b87c8f5bea501adee8cd8355","datavalue":{"value":{"entity-type":"item","numeric-id":930892,"id":"Q930892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$37234DFB-A2BD-4AB0-9B75-0EA41288BD86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed720c7f8a426d8aedd4fdfda06f652828568106","datavalue":{"value":{"entity-type":"item","numeric-id":5458503,"id":"Q5458503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$27B74749-689F-4DA5-8737-3570BABF621E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"deb93e3fbf679972f745fe18037190622afdafee","datavalue":{"value":{"entity-type":"item","numeric-id":659724,"id":"Q659724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$CB750502-6ADB-4C70-BBB3-8F79874DD317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"602080106009c6cc390d60ef107c044702ceb5fc","datavalue":{"value":{"entity-type":"item","numeric-id":3614030,"id":"Q3614030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$3C8B0E1E-97EA-4042-A618-BDD2F644FB52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5d44b0768db07357eda1d235a428f7ec777b530","datavalue":{"value":{"entity-type":"item","numeric-id":3990224,"id":"Q3990224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659685$38BFD8D1-D3CC-4943-AB8B-29F9602D04CD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"45c2b0c1f24343de7695ff925e6284e42a309df7","datavalue":{"value":"10.1007/S00373-010-0965-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659685$E45218A1-263F-455F-8C20-BDC6A0160D8F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3516f839ed1ff233864f09208248d7f75ea999e","datavalue":{"value":{"entity-type":"item","numeric-id":3134394,"id":"Q3134394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"293ba42f00dae5cb534ad778916f942d5bee5d20","datavalue":{"value":{"amount":"+0.8869866728782654","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":"Q659685$2B85485B-02A6-49B9-AEB2-2BC29AA17DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"865467f1d9c3de3e3bd90cfb33a23259c4254653","datavalue":{"value":{"entity-type":"item","numeric-id":5189512,"id":"Q5189512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcb92a82a21d7d215bb584bc447d2b6fdec81675","datavalue":{"value":{"amount":"+0.8857514262199402","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":"Q659685$5BBA7D4F-ADD8-4124-A8A3-0AA17852FF5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b05b65af6f4d97cdc54614ec89314c7cc643860","datavalue":{"value":{"entity-type":"item","numeric-id":4604118,"id":"Q4604118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e83f1e8702bd56b6eeaf6ffa3063ef8c3bb0ef5","datavalue":{"value":{"amount":"+0.8229156136512756","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":"Q659685$1EF2478D-DDA2-44FD-BEED-C39FD5B3460F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6dc9f2b9dca08d95189b358392dfd6fae93756e","datavalue":{"value":{"entity-type":"item","numeric-id":2449081,"id":"Q2449081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"835b807224dcdb086932a30f07cf184c6a431a17","datavalue":{"value":{"amount":"+0.8137964606285095","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":"Q659685$6C654903-5D88-4924-9F19-59AD86F6C7EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0af4fb0f1043c369548c11e30e809add6a6109b","datavalue":{"value":{"entity-type":"item","numeric-id":300254,"id":"Q300254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cd4ae590d4ebac9b1a491660b5c80c770a4e814","datavalue":{"value":{"amount":"+0.8103234171867371","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":"Q659685$75768AB5-6070-4D03-B6FB-79EE288327BC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Cleaning with brooms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Cleaning_with_brooms"}}}}}