{"entities":{"Q1306928":{"pageid":1317678,"ns":120,"title":"Item:Q1306928","lastrevid":67513926,"modified":"2026-04-12T18:30:27Z","type":"item","id":"Q1306928","labels":{"en":{"language":"en","value":"Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1348192"}},"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":"Q1306928$552196FC-A21C-436C-B4FE-F9150B24717F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7314968cf8c795d64a048ad099272ccf93389adf","datavalue":{"value":{"text":"Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1306928$CB1DB3D6-1692-462E-8545-8E45FB527258","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f11cb80a7d1b91b9596c1687799e1b9c2b18fdbc","datavalue":{"value":"0935.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306928$39D0F17C-DDC2-4C39-B1DF-56D7ED94203D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$7FD8B15D-6DE2-48E7-979F-EFA9FAC66B81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"06f41783cb6eb3a86211d59cba9ff7b62f6ba634","datavalue":{"value":{"entity-type":"item","numeric-id":293602,"id":"Q293602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$FC88274C-2C5D-45E1-B204-784F3A1D8D00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a112fcddf40de3e0f26627c12549da4365ccc05","datavalue":{"value":{"entity-type":"item","numeric-id":214987,"id":"Q214987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$5133FD97-E28C-43A0-966B-11C6FF479591","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$5913E3E0-92C7-4C3E-AF48-8AEF47A231D2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bc2df620fd6a8df372731edb4d2b9ffdc4ef3885","datavalue":{"value":{"time":"+2000-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1306928$C3C16ACB-D300-40DD-815F-51434F863A35","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9bdb57c547ef6a64468c30fffb3c1f0e61da008b","datavalue":{"value":"The edge-integrity of a graph \\(G\\) is defined by \\(I'(G)= \\min\\{|S|+ m(G- S):S\\subset E\\}\\) where \\(m(H)\\) denotes the maximum order of a component of \\(H\\). \\textit{K. S. Bagga}, \\textit{L. W. Beineke}, \\textit{M. J. Lipman} and \\textit{R. E. Pippert} [Congr. Numerantium 60, 141-144 (1987; Zbl 0664.05039)] called a graph honest if its edge-integrity is equal to the order of the graph. \\textit{M. J. Lipman} [Congr. Numerantium 85, 184-192 (1991; Zbl 0765.05094)] showed that there are exactly twenty honest cubic graphs. Here the authors prove that any honest graph with maximum degree 4 has at most \\(10^{60}\\) vertices but that for \\(k\\geq 6\\), almost all \\(k\\)-regular graphs are honest. The question of whether the number of 5-regular honest graphs is finite remains unanswered. It should be noted that \\textit{L. W. Beineke}, \\textit{W. Goddard} and \\textit{M. J. Lipman} [Ars Combin. 46, 119-127 (1997; Zbl 0933.05072)] had previously shown that for sufficiently large \\(k\\), almost all \\(k\\)-regular graphs are honest.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306928$FEB66F52-53D9-45DE-AE87-FBCCA283053E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306928$181985D1-983B-4C89-B83F-71F76336661C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306928$D40C8FDE-52EE-42CC-A4E4-82B017D784F3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f478a1ac787decc796f0a34f3293c42edd00ac71","datavalue":{"value":"1348192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306928$AFC8152E-7C7E-4267-B129-50CBFA69BDD8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b9dcbd299bcbb211d801a3f4d5d04cdddcc38f7","datavalue":{"value":"edge-integrity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306928$D1053929-534B-4701-8CBE-BBF7B9A1FCF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"237acb205fce73d8fe2b60d940aa81e2c6af1367","datavalue":{"value":"honest graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306928$14185889-830E-43F6-B8F7-45B8BF982BF7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4160ba73cc613e2769e008ae8a9ce69c96d8603f","datavalue":{"value":{"entity-type":"item","numeric-id":207053,"id":"Q207053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$832F746C-D0BF-4F61-A472-5FD7C53FE6AF","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":"Q1306928$0C95567E-2DA4-46E2-9496-EF573E7237D1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4d232acf26e9d9ca9da882b8128335ea39e26a3c","datavalue":{"value":"https://doi.org/10.1006/eujc.1998.0295","type":"string"},"datatype":"url"},"type":"statement","id":"Q1306928$5C3C1B81-B1A4-4BF1-BA42-119CDD1795CD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ce036ec32692040dc6a4efeea14637c8bc55d950","datavalue":{"value":"W1995059637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306928$6A5035E7-E027-45FD-A171-FB421703BF36","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0ac931768cf5405515bfb7d00781064cc5d4552","datavalue":{"value":{"entity-type":"item","numeric-id":4348783,"id":"Q4348783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$61F99FD1-CF1D-48FE-833E-B0AA0A70BDDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0df8c16fb6d4d3c861f57e0569695f268c7efadd","datavalue":{"value":{"entity-type":"item","numeric-id":800384,"id":"Q800384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$837932A9-C091-492C-BB2F-EC6DDA1D8EBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$43BE5BDF-C4AB-4B24-8180-5A312BC820F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb1823dbbf8fc7260b2233fd9532326e1aeb7dab","datavalue":{"value":{"entity-type":"item","numeric-id":3815334,"id":"Q3815334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$47070DFB-19D8-4B21-BF02-FE6C85EF980E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f09c3b001cbfb9c391a25120cf8b455b0a2f3449","datavalue":{"value":{"entity-type":"item","numeric-id":1313844,"id":"Q1313844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$854AA224-7B7F-46F1-AD0B-DF0BB4606883","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d88001a2f34e2beb6ce71bcd3f8f8ac4106f98fe","datavalue":{"value":{"entity-type":"item","numeric-id":3789603,"id":"Q3789603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$ABDC55FA-41B3-4601-860A-D94507217B9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8936264d645394bed1286a9c522b5e1431893330","datavalue":{"value":{"entity-type":"item","numeric-id":3781769,"id":"Q3781769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$28AA9405-3A1D-40A8-813F-2F3BFCEBE9AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f34fb167d6b58149e4c07bc6f477f173f3d07b81","datavalue":{"value":{"entity-type":"item","numeric-id":1150630,"id":"Q1150630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$FA2058B2-0408-4D86-AB0A-CB1075C9C4DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$C70F95A3-B527-4688-8B4A-4D4479EAF227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de613908d2cd012d4fcbd4fd9626fc061166750c","datavalue":{"value":{"entity-type":"item","numeric-id":1120601,"id":"Q1120601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$771E3E43-2BB6-4252-AED4-9F3389F4D4A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3817aea6492d84ff3696f1230aaf5ac9b3657e48","datavalue":{"value":{"entity-type":"item","numeric-id":1243484,"id":"Q1243484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$879CC788-420E-41DF-9F05-FD6BD4C0D9FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b9a315bc857914b22e6f23c0d8a62ad384132df","datavalue":{"value":{"entity-type":"item","numeric-id":4027167,"id":"Q4027167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$AB61F31F-89BA-4885-855A-AD32841A7400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbec918298f2da6fc8895f4aa7c453dddb02295e","datavalue":{"value":{"entity-type":"item","numeric-id":4028531,"id":"Q4028531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$0EF30270-05D8-4419-9D52-39665013B7E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10ccf4d42c4757827ddea695c7555934bd0854b7","datavalue":{"value":{"entity-type":"item","numeric-id":1112836,"id":"Q1112836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$5F9412E4-C12E-487B-9263-98C6E24D8E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1ed2ce67075a87cdb4040d4b3440a4f78bd3b15","datavalue":{"value":{"entity-type":"item","numeric-id":920104,"id":"Q920104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306928$009A91F5-B352-46D9-AE45-5FC3829EBB1C","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":"Q1306928$F3BA5CFD-D9F3-4303-B613-166B9D9C4BF3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2dd80745183423d761b0a4fb468c2d3d713cc282","datavalue":{"value":"10.1006/EUJC.1998.0295","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306928$3626E431-F54E-4437-81EE-641E742C506B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4920b23e366dd3eea6a6e2e38f06bbb1b10c842d","datavalue":{"value":{"entity-type":"item","numeric-id":4028531,"id":"Q4028531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd9b136bcda8a83f1772451c390ef173a9227477","datavalue":{"value":{"amount":"+0.8013508915901184","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":"Q1306928$D8026554-0C72-4743-B7E0-98E4FDA7988A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36a8ffa9431241744b7fc9c3733b310db33619f5","datavalue":{"value":{"entity-type":"item","numeric-id":4940043,"id":"Q4940043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e425b84c965109a9e64879a52cd98f283bf7af37","datavalue":{"value":{"amount":"+0.7963913083076477","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":"Q1306928$2C5EE496-84F5-4516-BC62-72B57ACD2AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a59a3322bf56256d7b3e7fb2d0affa047e5220b4","datavalue":{"value":{"entity-type":"item","numeric-id":2744372,"id":"Q2744372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb7f521f4cd67f5fb64f3b4ba2cc9b79195d5c1c","datavalue":{"value":{"amount":"+0.7722782492637634","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":"Q1306928$0D4D3BEE-8796-4C80-98B9-EF8A060AFFA6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Regular_honest_graphs,_isoperimetric_numbers,_and_bisection_of_weighted_graphs"}}}}}