{"entities":{"Q6544518":{"pageid":14155672,"ns":120,"title":"Item:Q6544518","lastrevid":55667572,"modified":"2026-02-17T20:41:15Z","type":"item","id":"Q6544518","labels":{"en":{"language":"en","value":"Weak external bisections of regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7854111"}},"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":"Q6544518$67E5CCF0-F386-41E5-87FB-5DDF1604BA09","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"838452abd90452598519fd8135de4940bd9676f9","datavalue":{"value":{"text":"Weak external bisections of regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6544518$41C54737-EDEB-4D14-B1E6-0FEB80E79825","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"13120b1e33cbafacfa708dc81c5134c7165671be","datavalue":{"value":"1544.05087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6544518$54DA7554-7783-4C0B-A9A0-D6D064DA9465","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1fb748b8d4d56b3a322da9b04781d4a5ce8f8d0","datavalue":{"value":{"entity-type":"item","numeric-id":709304,"id":"Q709304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6544518$43759DC6-F1E3-4164-AB45-A0CEDA2CA525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97d77712079c5c272edb5ecc96f94291f6c0270e","datavalue":{"value":{"entity-type":"item","numeric-id":6542009,"id":"Q6542009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6544518$2991460F-29FD-411C-B3FA-80FAC4C717CC","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":"Q6544518$5D1502BB-2AE8-4B11-A773-A7105C5E0AA6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eb446d46e1c3c1f4c9c481337a64fd2c7b9ecce2","datavalue":{"value":{"time":"+2024-05-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6544518$3CDC0F1A-ACA1-420A-8975-30CFA136FE24","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9f4f2001f751a411adc4f591fe3d3fa7700e8b36","datavalue":{"value":"The article works on classical graph theory. It is devoted to the partial solution of the graph bisection problem. A bipartition of the graph $G$ is a bipartition of the set of vertices $- V(G)$, with $V(G)=V_1\\cup V_2$ and $V_1\\cap V_2=\\emptyset$. If a bipartition satisfies $||V_1|-|V_2||\\leq 1$, that is called a bisection of the graph. \\textit{B. Bollob\u00e1s} and \\textit{A. D. Scott} [Random Struct. Algorithms 21, No. 3--4, 414--430 (2002; Zbl 1013.05059)] conjectured that each graph admits a bisection such that for every vertex, its external degree is greater than or equal to its internal degree minus one. In this article, the authors confirm this conjecture for some regular graphs. These results (obtained in the article) extend the results obtained by \\textit{A. Ban} and \\textit{N. Linial} [J. Graph Theory 83, No. 1, 5--18 (2016; Zbl 1346.05223)]. The authors also give an upper bound of the maximum bisection of graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6544518$051DEFF5-C398-4FCD-B0D0-94CDD038039B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6544518$351A41FF-6FB1-4D4C-A508-625B014D9594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6544518$B28C319A-E667-42D1-B3C7-B4898A39CA3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6544518$EA016B98-0B69-46DD-A722-F3FE8184E127","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4e01d2204eee55a3e857fd225b58b8c1437a468a","datavalue":{"value":"7854111","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6544518$A8A9505B-16AC-4123-AE10-341D51B226CA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3c312f4cdb785ebb78dd72c24a4fc6cb39b203e","datavalue":{"value":"external bisection","type":"string"},"datatype":"string"},"type":"statement","id":"Q6544518$46482D96-9535-44CB-92C5-6AF706AF600C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e46582e509cc6ba4a6da9b8342e2fce1380e6d3","datavalue":{"value":"maximum bisection","type":"string"},"datatype":"string"},"type":"statement","id":"Q6544518$78C48BD0-5611-44C6-81DD-5985B3F0FAB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9217cf5fdf9311e03b0d651a5eac92fd9c7100c2","datavalue":{"value":"regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6544518$569E02C8-D63E-47A3-A2FD-A9AB731166C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"433046c6aa9b740fa40639148bd6c6d64f59a1c1","datavalue":{"value":"2-factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q6544518$56530C62-0B98-4C87-8F74-F103D555EDCA","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":"Q6544518$B21DFBB3-ABEC-4221-84CD-F00B960F7C5E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9759af6568db2190bc489d60d0b9408c7b3e556c","datavalue":{"value":{"entity-type":"item","numeric-id":2825476,"id":"Q2825476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6544518$76F12A59-83FC-480A-B131-D7BD95A0FD39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f618b68e64de76d8cd4ee93f4ffc8be068a2977a","datavalue":{"value":{"entity-type":"item","numeric-id":4798176,"id":"Q4798176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6544518$8642264B-7EF0-4A98-80C1-BB2676BAC529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef7621cd4ee7fa643aeac1503d770f247d7a5bf0","datavalue":{"value":{"entity-type":"item","numeric-id":4650188,"id":"Q4650188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6544518$418D6FDE-86A1-45A8-A2C3-02737D1FD17D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9b365825a6b044863e94d1e359b4d6ae902eef4","datavalue":{"value":{"entity-type":"item","numeric-id":2279266,"id":"Q2279266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6544518$7E25747C-157B-493F-88FF-76B73DE1FA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca1f177b2ce915fd9ee2eb69a43ba2095c49d083","datavalue":{"value":{"entity-type":"item","numeric-id":2338639,"id":"Q2338639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6544518$28D6687B-E3C4-4A0C-84EA-850DAC9DD73E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"847c7d985c6b62a505e47c8249acd80b095dbf3e","datavalue":{"value":{"entity-type":"item","numeric-id":461728,"id":"Q461728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6544518$EBC26670-3D08-4BC5-8D06-BB492CA317D7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"24469bafaa07e8ad78317fe90843e6c78830ea4f","datavalue":{"value":"10.1007/S00373-024-02796-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6544518$E24473CB-86B3-4E33-9045-3BC8B848C17A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44789fadaf2d74adf9eceba074a728bce638e7f9","datavalue":{"value":{"entity-type":"item","numeric-id":402590,"id":"Q402590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b3b4541f8228544d9b3d061883528ac646283d2","datavalue":{"value":{"amount":"+0.8416244387626648","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":"Q6544518$216CC772-74EC-4698-A388-58469DE1AB89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c9d3131b409243875e44ac55b54b535419bacee","datavalue":{"value":{"entity-type":"item","numeric-id":461728,"id":"Q461728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b260e7f6b98903a9f42f11b1ab9143c46de0539","datavalue":{"value":{"amount":"+0.8231180906295776","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":"Q6544518$79ABE34D-48C5-4F1C-AC4B-7C81A99684DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0ee286ad8f1fde6fef20931c61a27693aa672be","datavalue":{"value":{"entity-type":"item","numeric-id":5190331,"id":"Q5190331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce31368bfb52cb5a4e78cefc09918a867bd3f5e7","datavalue":{"value":{"amount":"+0.816053032875061","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":"Q6544518$2F258C93-91D2-4072-ADD7-922BB0BCC09A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"855da618046a3f97129d1fd02ebe4917fe5838ee","datavalue":{"value":{"entity-type":"item","numeric-id":3402776,"id":"Q3402776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0c4307977f9706afdb2cf3a61e30645b78b2de0","datavalue":{"value":{"amount":"+0.8085790276527405","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":"Q6544518$EDD386B8-C26C-467C-9270-D23628E7FB97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6002c1498153a2b03378a8501df94ed6d4c8f6bb","datavalue":{"value":{"entity-type":"item","numeric-id":3195864,"id":"Q3195864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0e8957c1f92abb6ceee82173e9b233528ee06b6","datavalue":{"value":{"amount":"+0.8025343418121338","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":"Q6544518$C8296513-6ECF-463C-814D-9FF9D1D66795","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6544518","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6544518"}}}}}