{"entities":{"Q1917282":{"pageid":1928024,"ns":120,"title":"Item:Q1917282","lastrevid":69297885,"modified":"2026-04-13T06:04:38Z","type":"item","id":"Q1917282","labels":{"en":{"language":"en","value":"Graphs with largest number of minimum cuts"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 897389"}},"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":"Q1917282$566C2178-1AB2-43A8-9C7F-CFF4C5AEC264","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bdf110f30819a41bfd6273360cdd16c431ba30f5","datavalue":{"value":{"text":"Graphs with largest number of minimum cuts","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1917282$96695BB6-B898-40B6-898A-812E1FC88987","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"71d192aa59ae64099e3459280ebbb2b780d9cc34","datavalue":{"value":"0858.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917282$1062AFFA-35A0-4AF4-9729-A96ADD2DD777","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"85eb217c688ce789aa0518494e5ee9dfd2e2bf68","datavalue":{"value":"10.1016/0166-218X(95)00043-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917282$DCABEADB-1BC9-4E10-981F-7C025953D9ED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec2d7eb4aa6a054061ffef53b12788916e0dba01","datavalue":{"value":{"entity-type":"item","numeric-id":222618,"id":"Q222618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$84BE2C50-1821-422A-8D20-A74A90BD02A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6eccd330e58db916925e9726f6d3cc506f17a2da","datavalue":{"value":{"entity-type":"item","numeric-id":442401,"id":"Q442401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$4438096D-2E6E-4E61-8799-B052580BB328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d40587e04768d5f70473e58fb8ddc324137351a9","datavalue":{"value":{"entity-type":"item","numeric-id":185069,"id":"Q185069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$54DAFC46-5C23-43B2-B87A-14C9F4D359FB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$A09057F5-7CF5-4C75-8F7F-784306C4EDBE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ec21ef37bce0805fb00f1ca104e0c5eae04ad1ef","datavalue":{"value":{"time":"+1997-03-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1917282$1ADE8244-3B43-4A24-8968-D0D96C6D52A9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"367429eda324fc7939fc73f9aa90dff45e958551","datavalue":{"value":"Denote by \\(\\sigma(n,k)\\) the largest number of minimal cuts in a \\(k\\)-connected multigraph with \\(n\\) vertices. It is known that \\(\\sigma(n,k)\\leq(\\begin{smallmatrix} n\\\\ 2\\end{smallmatrix})\\) if \\(n\\) is even and this bound is tight. The authors prove that for an odd \\(k\\geq 3\\) it holds \\(\\sigma(n,k)\\leq \\lfloor 3n/2\\rfloor-2\\) and characterize the graphs with \\(n\\geq 4\\) vertices for which this bound is tight. A similar question is also studied for simple graphs, where the corresponding number is denoted by \\(\\sigma_1(n,k)\\). For even \\(k\\geq 4\\) it is shown that \\(\\sigma_1(n,k)\\leq 2(n/k+1)^2+n(k-1)/(k+1)\\) and that this bound is tight if \\(k+1\\) divides \\(n\\). For odd \\(k\\geq 7\\) it is proved that \\(\\sigma_1(n,k)\\leq(1+4/(k+5))n\\). For \\(k=3\\) and \\(k=5\\) all extremal graphs are characterized.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917282$CF5C9C68-3DF3-4AB9-A270-77E786D8E30C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f12e1eb1be75d4426df498c29926dc868c2e1814","datavalue":{"value":{"entity-type":"item","numeric-id":187114,"id":"Q187114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$3D8268D5-645D-437B-97E2-82687BC87997","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917282$750C70C5-78E9-47D7-A664-67B9AB8D4BC1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c7cc489328f00f58d1bdad724d045c5804dad5d9","datavalue":{"value":"897389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917282$0238DC23-6060-4F90-876E-26B17E6945A4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917282$5C8F6AEC-40EA-43F8-9B47-D3C084AC9177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1262d51f50334708902b19dcd78f24e1a994f9ba","datavalue":{"value":"cuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917282$61F31FF6-E33F-4767-9065-569AD6CA7B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bdefd4725d91bba1e0d0861018fdd0e81ad28b3","datavalue":{"value":"extremal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917282$F2CC60EC-BD14-4D85-A7C3-8F06E5146F34","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":"Q1917282$DEB6ACBB-CCD5-47DB-A4FC-931522456167","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8396d8d81694d9207e42463cf8d371948e36190","datavalue":{"value":{"entity-type":"item","numeric-id":4073398,"id":"Q4073398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$2F705B64-97ED-4CDF-81F6-34A33D6BE07D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44c662692a038795c15512155172fbcd5936da4e","datavalue":{"value":{"entity-type":"item","numeric-id":4200096,"id":"Q4200096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$93540851-5871-4000-B5CF-25C171605149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c45c86c7f172e023843236094a98399ae49d365","datavalue":{"value":{"entity-type":"item","numeric-id":4165177,"id":"Q4165177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$7FBD4CBA-28A2-4B62-B3AC-C61E99ED11D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb8c15014e2ce921e9154dc859703b736262b19b","datavalue":{"value":{"entity-type":"item","numeric-id":3032277,"id":"Q3032277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$0A6CCD77-F7F6-4F28-B76D-5F0F0894CD1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4b40a0873cef5b51bd21f9e736ad604a9753a4f","datavalue":{"value":{"entity-type":"item","numeric-id":3218167,"id":"Q3218167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$36B8E910-A94A-4ADB-A740-35893DEAB363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc3daf7de14aeb01da885b4ed98fe4e8dcc1494e","datavalue":{"value":{"entity-type":"item","numeric-id":3987534,"id":"Q3987534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$D2F4E997-8BE4-43F8-ABB4-CACCC08EC416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fa13b7f3fc3881eb5fd50e73fd173d48e938b02","datavalue":{"value":{"entity-type":"item","numeric-id":2543431,"id":"Q2543431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917282$BD67DC64-D9C4-46B2-BF85-C321E7284A1A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1571a258e731be96a9fba582533e39de647821b","datavalue":{"value":{"entity-type":"item","numeric-id":3344017,"id":"Q3344017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d315aa938b1c29c2fe92d20215c39c407a73040e","datavalue":{"value":{"amount":"+0.8344913125038147","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":"Q1917282$DAD36473-452B-4B46-85D0-FAEF04F62737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b47f3f21c1d8dba0b01c7f9b3d0b8b23cc693c83","datavalue":{"value":{"entity-type":"item","numeric-id":4319529,"id":"Q4319529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b1093855a96772637fd4a95a6e10810488d4af0","datavalue":{"value":{"amount":"+0.8234549164772034","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":"Q1917282$6FC85AC5-A28B-4891-B88E-0F8B517EBAC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ced77d62c292ed5b56405a3c4426f6f8300a8239","datavalue":{"value":{"entity-type":"item","numeric-id":291167,"id":"Q291167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfd5e2ec96b23fc4fa470b3d31864feceb73d999","datavalue":{"value":{"amount":"+0.7974587082862854","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":"Q1917282$25F3423A-4E7D-4582-BB43-4B1EBBD70441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bde994a2fe8a4343839c3833e5785f3e689b3ed1","datavalue":{"value":{"entity-type":"item","numeric-id":3987534,"id":"Q3987534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20f1b7f816e159ad770e6febaaf7cc301ca0082c","datavalue":{"value":{"amount":"+0.7970815896987915","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":"Q1917282$2AE17926-4DE7-4D6D-8A68-33ACF11530C3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs with largest number of minimum cuts","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_with_largest_number_of_minimum_cuts"}}}}}