{"entities":{"Q1905161":{"pageid":1915903,"ns":120,"title":"Item:Q1905161","lastrevid":73269333,"modified":"2026-04-14T15:13:11Z","type":"item","id":"Q1905161","labels":{"en":{"language":"en","value":"Computing the isoperimetric number of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 830620"}},"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":"Q1905161$64935C0B-5A94-41DE-84E8-AA391132A7CD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f268d469da3f5e8e1484be86075d076141e53ec0","datavalue":{"value":{"text":"Computing the isoperimetric number of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1905161$36286876-5DE0-439B-B528-B02459C328B7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51a0e9d8d643abffc40afab7a8531d4c88afd56d","datavalue":{"value":"0835.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1905161$A47E49A5-5D2F-4649-AA70-762100D57731","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e5f10541890f8284f2a046dcb64148a083a0d0cb","datavalue":{"value":"10.1007/BF02366479","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1905161$2F0FEA2A-320F-4E9B-881E-1E54A47ED8D0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1b023419c56b9969f2d98b08637e9b0af86a936b","datavalue":{"value":{"entity-type":"item","numeric-id":199816,"id":"Q199816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$9789992B-FE9A-44B1-BC71-5811ABFF163A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"47d6ab12c78e00de61a379bc2110f938e4be3823","datavalue":{"value":{"time":"+1996-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1905161$949F6C06-519B-499B-82E9-9D89D60D59EB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf5d4f16f3bf4f3bdb5fd82d32be1424289e51a2","datavalue":{"value":"Let \\(G\\) be a finite graph. Denote by \\(\\partial X\\), where \\(X \\subset VG\\), the set of edges of the graph \\(G\\) with one end in \\(X\\) and the other end in the set \\(VG \\backslash X\\). The ratio \\(i(G) = \\min |\\partial X|/ |X |\\), where the minimum is over all nonempty subsets \\(X\\) of the set \\(VG\\) such that \\(|X |\\leq |VG |/2\\), is called the isoperimetric number of the graph \\(G\\). It is easy to see that the isoperimetric number may be used as a ``measure of connectivity'' of the graph. The problem of determining the isoperimetric number is clearly linked with graph partition problems, which often arise in various applications. The isoperimetric number is also important for studying Riemann surfaces. These and other applications of the isoperimetric number justify the analysis of graphs of this kind. The properties of the isoperimetric number are presented in more detail in [(*) \\textit{B. Mohar}, J. Comb. Theory, Ser. B 47, No. 3, 274-291 (1989; Zbl 0719.05042)]. A similar construct for infinite graphs has been considered in other papers. It is shown in (*) that the computation of the isoperimetric number is an NP-hard problem for graphs with multiple edges. We show that the decision problem ``given the graph \\(G\\) and two integers \\(s\\) and \\(t\\) decide if \\(i(G) \\leq s/t\\)'' is NP-complete even for simple graphs with vertex degrees not exceeding 3. Note that the isoperimetric number of a tree can be computed by a known polynomial-time algorithm, see the Mohar paper mentioned above.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1905161$1A6E010B-9852-46C6-9DBF-EA33F4457F14","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1905161$57371518-A440-4B21-9991-62DAED28E9DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1905161$B536BB54-A4A7-4953-8CC4-948B7237366F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1905161$740E34BA-26D0-4CD7-B1A8-F96973EEEC42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1905161$2FB656CF-0C06-4777-9FF6-4DFE93D4D507","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f2e73fe85bf47ccdba9a6bae4f77c7783b47e63","datavalue":{"value":"830620","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1905161$E148B9E6-5159-4452-9238-4001A319D203","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bfa7ad7cc229e2d9ec43c2e311ac196f27a13cb","datavalue":{"value":"isoperimetric number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1905161$B42F2851-38A9-4F27-8FE9-BC81D8ACF7D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"832405e003d774dce822c65e9e01ce531ed8c899","datavalue":{"value":"NP-hard problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1905161$F46A20C9-1C23-4F12-8328-7577A8B2D8E7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a4df628262abf79464ed4f15ac79f197844f8c4","datavalue":{"value":{"entity-type":"item","numeric-id":259036,"id":"Q259036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$AA845266-FEFB-4484-A654-A255CD902ACB","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":"Q1905161$BF765C08-A7FD-4FD4-92C1-DC237A25305A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6d60a5d3a0f978a279694c358f0385ac256a903","datavalue":{"value":{"entity-type":"item","numeric-id":3824448,"id":"Q3824448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$B770DA36-2B8A-4680-974C-6B2BFD5C63B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd84af9232febcdcfbac47b8ddbbe58f9800d7c6","datavalue":{"value":{"entity-type":"item","numeric-id":796548,"id":"Q796548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$2A692512-1B71-4EE4-98EB-A199E3BBED2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"383ffa39d4f987a6ae84cd3709e108f8363810f0","datavalue":{"value":{"entity-type":"item","numeric-id":4751110,"id":"Q4751110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$87D1DA7F-9606-4BF6-8ED7-03CE63DD3483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$BA64113B-0CDA-47EB-9024-9BE2D7A376E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec4b4e745761de5ad8451158ee41abbbc4a56c74","datavalue":{"value":{"entity-type":"item","numeric-id":3752395,"id":"Q3752395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$E492D293-4D0E-4E78-A655-34F58E8ECB4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"645b2999f4ba18733e6680c85fa03c214cb4fbea","datavalue":{"value":{"entity-type":"item","numeric-id":3347934,"id":"Q3347934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$87F8E4F4-5B15-4716-8CF5-4DE80BB10C24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c6036ea89b7fffdbcb3d148f24dcf60fd10091","datavalue":{"value":{"entity-type":"item","numeric-id":1111573,"id":"Q1111573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$E9CA5D26-5CF4-4679-AB19-4D2715323FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458c098ba6ad6e3c5eda6d5eb7f8a6fc6420a8b2","datavalue":{"value":{"entity-type":"item","numeric-id":2639872,"id":"Q2639872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$E7A6495C-F7C0-43DA-9055-E6402BB0BEA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c905fe3a03c754f92fd6d63a21e870af487c208","datavalue":{"value":{"entity-type":"item","numeric-id":1063327,"id":"Q1063327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1905161$708402BA-7F33-4D11-BAA6-B758896C1DC4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e8ab1e6b4bfcb818ab5073f68df514726980dba","datavalue":{"value":{"entity-type":"item","numeric-id":765346,"id":"Q765346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d5cbaccc66124bcbb36d3752831096815aefc89","datavalue":{"value":{"amount":"+0.8521234393119812","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":"Q1905161$FA531374-653D-493C-B87C-E0DCA30E86DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d658e371f828e2e0637883979b9bf65af1245df2","datavalue":{"value":{"entity-type":"item","numeric-id":2639872,"id":"Q2639872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dd1decbdaad7400f74720ea07a5b3d9bdf78f2e","datavalue":{"value":{"amount":"+0.7852351665496826","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":"Q1905161$53A1E8B1-B622-4B55-BFAB-30F3FFBE47A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"313e001b8a1e3d84fc0442bf013f767fd5e0da07","datavalue":{"value":{"entity-type":"item","numeric-id":974467,"id":"Q974467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3014ac7eca4756922ea30a1f0a63296768d4e5f4","datavalue":{"value":{"amount":"+0.7613900899887085","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":"Q1905161$CFF18344-51C5-4998-B8AD-D39363EF1948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33af9c3262712bf0cbe235a97dbadf43e8277935","datavalue":{"value":{"entity-type":"item","numeric-id":5469407,"id":"Q5469407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f132133943f6eed2bc3ce849aa0d4f16a2d98568","datavalue":{"value":{"amount":"+0.7456604242324829","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":"Q1905161$2484DC94-148A-4933-AB8B-68B992107B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad377ec99ea586a655a7a125b1653837540ed74d","datavalue":{"value":{"entity-type":"item","numeric-id":4598229,"id":"Q4598229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"802abdf85dd62e4e2bcbdd982b51c26104508d95","datavalue":{"value":{"amount":"+0.7428304553031921","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":"Q1905161$7F528D7D-B995-4261-8BDF-7D31381523D8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing the isoperimetric number of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_the_isoperimetric_number_of_a_graph"}}}}}