{"entities":{"Q1077429":{"pageid":1088181,"ns":120,"title":"Item:Q1077429","lastrevid":66670320,"modified":"2026-04-12T11:44:26Z","type":"item","id":"Q1077429","labels":{"en":{"language":"en","value":"Subgraphs intersecting any Hamiltonian cycle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3957154"}},"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":"Q1077429$1AB45483-2C67-427B-A8C2-48D82D7DBD34","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c8b052bbc87bd81c2d4af2e775cdb84d328c1070","datavalue":{"value":{"text":"Subgraphs intersecting any Hamiltonian cycle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1077429$143B2DA5-7A06-465E-894A-6D1C69E2A645","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ac8798c21df299634f577fc7ba3bfb9eb6ab20ff","datavalue":{"value":"0595.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077429$B0A1E875-F7BB-4807-9143-A3CF44BC9B90","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e52143f8ce3f0b210136ac0d3eb85cdbf9e68c9b","datavalue":{"value":"10.1016/0095-8956(88)90097-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077429$F845EB08-4966-422B-8918-FBFBD1BA75F3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$FAA93C40-49BF-48D3-8AB9-5A9B516C131C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1077429$F3ECE60B-5C56-4DAF-9180-AA0B1B3C0F86","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a3f13023427c89e16a63b5973d2bd2c232da027d","datavalue":{"value":"Let G be a subgraph of K(n), the complete graph on n vertices, such that (i) its edges cannot be represented by fewer than k vertices, (ii) every hamiltonian cycle of K(n) contains at least one edge of G and no proper subgraph of G has this property.    P. Erd\u0151s posed the question of determining min e(G). In particular, is there an absolute constant c such that e(G)\\(\\geq c\\cdot k\\cdot n?\\) The minimum is calculated for all \\(n\\geq 3\\) and \\(k\\leq n/2\\), and the second part of the question is answered in the affirmative with \\(c=1/4\\) being the best possible constant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077429$883B01F1-9479-4ABB-A101-407D5F8862BD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077429$681555CC-CEBD-45E1-BC7B-A1A1538839E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077429$4BA22F46-5E8D-49EC-9741-B601C9679E2F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e1cdcfe5562c46ebb84923e6adf22132996c1db6","datavalue":{"value":"3957154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077429$21C6AAD1-9D3E-4ADD-9A9B-4DD3DA9B04CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95315580a488697753f314bcf92d6e8b4a36f135","datavalue":{"value":"vertex covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077429$7EB525C8-763C-44CC-B85E-7D848FC3980B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b18fbe770dd6442dcd3b11d19d68457707d1374d","datavalue":{"value":"maximal non-hamiltonian graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077429$CA3DBE52-A910-4566-882D-62413677683C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e87bb1aed89f5da6ee5d1aa38eb687932a17c03","datavalue":{"value":"subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077429$8A791A38-91BA-4E1E-9591-C6B107332980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ec6cafaf78f34592a470a0bda5aa4ea1f712345","datavalue":{"value":"hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077429$1370202A-537B-457F-BA69-8DC68EDE5BE4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e71d1531addd3e751a7c2f29dcec31264ed06413","datavalue":{"value":{"entity-type":"item","numeric-id":215558,"id":"Q215558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$4B2C55AC-CC37-4FB7-A033-4F62E8C7F5B5","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":"Q1077429$B19897F6-F97C-4E7A-AD18-F949D49018C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"30cf0d32f2b9bb69e56bc9b5a34ac9c8375bdfac","datavalue":{"value":"https://doi.org/10.1016/0095-8956(88)90097-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1077429$E807FA72-09D5-45C7-8750-EEC311CFF363","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0f72d175c2cb976f8b83e95fcaa26c3b6445049d","datavalue":{"value":"W2082969553","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077429$6BA806B0-CBE7-45B6-85D8-49C693ED4562","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdc91c6e93789ee17e248c1697a54c42f85472a6","datavalue":{"value":{"entity-type":"item","numeric-id":5648389,"id":"Q5648389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$52F90E58-576A-43F6-B66A-AFA50BDEF869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd492719f080c59c4dd23730fc178cf5a672a45","datavalue":{"value":{"entity-type":"item","numeric-id":1227760,"id":"Q1227760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$B96CE159-D6D4-48B9-BBD0-2E175DE3AE30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11fbb5ee59c3c5fba8b68dc26e64c473270f6227","datavalue":{"value":{"entity-type":"item","numeric-id":2545100,"id":"Q2545100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$B855C53A-DB4D-4E96-8D41-1947F41E7A26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c743424de859b331f95293d9a28c4c6a188a467","datavalue":{"value":{"entity-type":"item","numeric-id":5722820,"id":"Q5722820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$1503450A-69DB-497D-8606-2773F632CCE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81c84646e925b98c1f203d8d083e499b69ddfa37","datavalue":{"value":{"entity-type":"item","numeric-id":3337470,"id":"Q3337470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$893502F0-262D-4BCA-A80B-DDDA7A140970","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4534d792f5262a1f297a74f9b43efedcc5cd94ec","datavalue":{"value":{"entity-type":"item","numeric-id":4760022,"id":"Q4760022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$9C3D835C-2F51-43F2-AD69-7001C4B954AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22246ff69c3ce611b8b52b16a6e67b8fa225645e","datavalue":{"value":{"entity-type":"item","numeric-id":1087884,"id":"Q1087884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$24A98181-F847-447E-8786-631E573793F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4873262ef1cd18bae17898f37af6fa8892a64114","datavalue":{"value":{"entity-type":"item","numeric-id":1161757,"id":"Q1161757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$F7658581-B70A-4F14-A46E-A727672261F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb3b7fb38cb67438d9ac0e86da860270190ce82b","datavalue":{"value":{"entity-type":"item","numeric-id":774916,"id":"Q774916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$577D4822-E47A-4DE6-A581-9D34FD1B10A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56b6b49e719bb2c7ce3b0c67a6884eac14720016","datavalue":{"value":{"entity-type":"item","numeric-id":3884141,"id":"Q3884141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077429$C00F2199-A495-412D-AA3B-A6D1CEF8DA3C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0afd3b0500e88af83403b0f9c331bdc08124baab","datavalue":{"value":{"entity-type":"item","numeric-id":4871162,"id":"Q4871162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dcf86c88741eb688a9f17243fdf53cc5dafb4aa","datavalue":{"value":{"amount":"+0.802762508392334","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":"Q1077429$889078D6-A824-47E9-8C3C-C33E7412F926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ed8be3dec899f8c9c92e63d15563a9d49c0068a","datavalue":{"value":{"entity-type":"item","numeric-id":3317136,"id":"Q3317136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dcf86c88741eb688a9f17243fdf53cc5dafb4aa","datavalue":{"value":{"amount":"+0.802762508392334","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":"Q1077429$AC7BE056-918D-4C2A-9E6C-21B63A5AA2BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04841948fb0c4e4680c3701b8dd37023b5caec48","datavalue":{"value":{"entity-type":"item","numeric-id":3469119,"id":"Q3469119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58b66dba3be56bb0869f4b2a28c55a2005a5f5b3","datavalue":{"value":{"amount":"+0.8017100691795349","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":"Q1077429$E8B3548B-E668-423A-9E06-62956696EEE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14097bcfdb34e441f43283f22e5ee9ea7b17b071","datavalue":{"value":{"entity-type":"item","numeric-id":1336706,"id":"Q1336706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dc1fe251e85293072582f7584be3e3c76ee7c13","datavalue":{"value":{"amount":"+0.7913351058959961","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":"Q1077429$0589272F-7A37-4C47-A3D0-C75752A1F8A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19b497183acd903ae42875b696b9e517e276eef5","datavalue":{"value":{"entity-type":"item","numeric-id":3481737,"id":"Q3481737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbf8d62c7f1c03e90f1f1ad1beab22112fef43d8","datavalue":{"value":{"amount":"+0.7875269651412964","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":"Q1077429$BEB57E9A-156A-4BC0-8653-D3A1EF74A1DE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Subgraphs intersecting any Hamiltonian cycle","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Subgraphs_intersecting_any_Hamiltonian_cycle"}}}}}