{"entities":{"Q6080370":{"pageid":13214677,"ns":120,"title":"Item:Q6080370","lastrevid":55490350,"modified":"2026-02-17T17:34:22Z","type":"item","id":"Q6080370","labels":{"en":{"language":"en","value":"On a conjecture of Gr\u00fcnbaum on longest cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7745023"}},"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":"Q6080370$D4DC4682-ED12-418F-B86D-958B10BE134E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fdd2fc402b01dedf3bd2578754104c1d26de6d62","datavalue":{"value":{"text":"On a conjecture of Gr\u00fcnbaum on longest cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6080370$3FE1A719-5858-4591-9B0E-E6F869C3DA67","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1df88ad7cc9b385ac75815a4bf2f05f4715351da","datavalue":{"value":{"entity-type":"item","numeric-id":390296,"id":"Q390296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$F9AB3347-299C-4933-B98B-6C0250C6A3A5","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":"Q6080370$8EBAC7F7-1CE8-4234-BC47-563DE336FBB7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e68dcb3ce5566cf2b4bd7c1def923cc7a3f373d5","datavalue":{"value":{"time":"+2023-10-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6080370$F9695DBA-F684-424F-B114-00113577E147","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2d26b24a1049ff59fd9617b8547a61b1fc368d2a","datavalue":{"value":"\\textit{B. Gr\u00fcnbaum} [J. Comb. Theory, Ser. A 17, 31--38 (1974; Zbl 0259.05120)] conjectured that for any integer \\(k \\geq 2\\), there exists no\\(n\\)-vertex graph \\(G\\) of circumference \\(n-k\\) in which the removal of any \\(k\\) vertices from \\(G\\) yields a Hamiltonian graph. The author shows that for any positive integers \\(c\\) and \\(k\\) there is an infinite family of \\(c\\)-connected graphs of circumference \\(k\\) less than their order, in which the limit (as the graphs' order tends to infinity) of the ratio between the number of \\(k\\)-vertex sets whose removal yields a Hamiltonian graph and the number of all \\(k\\)-vertex sets is 1. Motivated by a question, a relaxation of Gr\u00fcnbaum's conjecture, posed by \\textit{D. Katona} et al. [Mat. Zametki 45, No. 1, 36--42 (1989; Zbl 0668.05044)], which states that whether an \\(n\\)-vertex graph in which every induced \\(k\\)-vertex subgraph is Hamiltonian must itself be Hamiltonian, where \\(k\\) is an integer satisfying \\(n/2 < k < n-1\\). In this paper, the conjecture is disproved for the case of \\(k=n-2\\). It is proven that there exists an infinite family of non-Hamiltonian graphs of increasing diameter \\(d\\) in which the removal of any two vertices at distance 1 or any distance at least \\((d + 6)/2\\) yields a Hamiltonian graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6080370$04C8677B-FE69-480F-B38C-F79C00A12708","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1bf9b495f81952c09c02d41528d44fb374f709fe","datavalue":{"value":{"entity-type":"item","numeric-id":409385,"id":"Q409385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$7E4A5E48-3B2C-4B68-B732-F5B9327766F3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6080370$9274F6FB-C988-44C9-A4A6-70F516B9E3DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6080370$8F122EE0-6682-44D2-A482-B157C45A8F93","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cbd0a57b61e0bee6ebd3e6eb6edfe3b30afc494c","datavalue":{"value":"7745023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6080370$FD8B8206-3172-445F-AFAC-9322FA494CD2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc7b4d2c7ddddbdcaefa50a42c56e156daf5fead","datavalue":{"value":"Hamiltonian graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6080370$12156A9E-A2B2-45E3-BFBB-E89DEA72F064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24bb3b9099154c0f5a16d2b4a10fda71d3228c16","datavalue":{"value":"circumference","type":"string"},"datatype":"string"},"type":"statement","id":"Q6080370$6343E978-FD33-4A90-B810-7FEE4C457727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f94b70e72af7511eb26bcafe85e780945bec9fe","datavalue":{"value":"Gr\u00fcnbaum conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q6080370$5FB41433-74B4-4E29-9921-B5E76E8B4CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eae9938a10a9ce236969ff4b37ad83a01ad6a8fb","datavalue":{"value":"\\(c\\)-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6080370$1FA8A4A0-4272-4550-9C44-7A3D559DB4F5","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":"Q6080370$DB672805-A340-45AD-A317-831C443A30F0","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e16fb5ecbd4ae00e41343df9dc700abb75a55705","datavalue":{"value":"Q123110230","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6080370$0ADAB55C-12EC-434A-BA12-A150627AA044","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ef2ad2e3fe9508e5b865d355824e80296abe2e70","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2023.103791","type":"string"},"datatype":"url"},"type":"statement","id":"Q6080370$4FED5FD2-DF64-4F3F-892C-D55E853203E0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e89d0e94bf5b6ba21d27015a3099d455ae95fd17","datavalue":{"value":"W4386010535","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6080370$CB2952AD-DD27-4D2B-88CF-59CF0679A4A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"743f0bc7b42cf22f12f4e18fe07a79e6ab0df4f7","datavalue":{"value":{"entity-type":"item","numeric-id":5666595,"id":"Q5666595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$5848EAB6-1BDC-4335-99A5-45C9F75F81F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ca26618e7a387b875a752f30340c3c8d669a267","datavalue":{"value":{"entity-type":"item","numeric-id":2560260,"id":"Q2560260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$ED3977B6-6125-461A-97C7-63A131E3E974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b3d5f7a1edd35ca8f1884a3251d279f95f8bdbe","datavalue":{"value":{"entity-type":"item","numeric-id":912130,"id":"Q912130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$090C8B6F-0652-4396-9D89-16CB9DD51A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0af858721480a2bdaeec78555a9a9ba519525af","datavalue":{"value":{"entity-type":"item","numeric-id":1394359,"id":"Q1394359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$31BDF938-0721-4C87-9925-3A3C5F0524F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc51da8b052ee5314dc35a998d2ef4e1d9c51ea7","datavalue":{"value":{"entity-type":"item","numeric-id":4146745,"id":"Q4146745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$FE7062E3-3AA3-46B1-9D9E-8668F2808454","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b50a40a84a8da2c4c187fd01c7bb2ddbe3662a8","datavalue":{"value":{"entity-type":"item","numeric-id":742591,"id":"Q742591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$ED5A73C6-BAED-43B4-AD5F-8690E9283600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5775c5dc5a856b8a322e15f576c8d2c22300c4b8","datavalue":{"value":{"entity-type":"item","numeric-id":5251202,"id":"Q5251202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$3D7D801C-5420-40AF-B728-47D4833FFDCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8428b78da0b8ad9950f7f2b125a89f3ec60b3ab","datavalue":{"value":{"entity-type":"item","numeric-id":5009329,"id":"Q5009329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$0A3B098B-5F3F-411A-A7EE-DEF746AE33D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05ea33e95bc0e045a0bedb7cb28c7f7f11937aca","datavalue":{"value":{"entity-type":"item","numeric-id":4581282,"id":"Q4581282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6080370$A461F7B7-8356-4FD2-A4C9-05EFB42606A8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"583821e628762a0e56fc71483292cde38456b1a1","datavalue":{"value":"10.1016/J.EJC.2023.103791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6080370$F502867B-D484-411E-8EE3-C05729DB112F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23ef2bbbc03bc2fc8bee5c064f92f37596203c1a","datavalue":{"value":{"entity-type":"item","numeric-id":3174236,"id":"Q3174236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"951f09424010c19c974af1f9ab08360bc241eb48","datavalue":{"value":{"amount":"+0.793035089969635","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":"Q6080370$ADF06C06-2A3C-4226-A3E7-8F135AC3876E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ff36bc8e6c9bd870e79fe8c2fad5947a2d0f0b5","datavalue":{"value":{"entity-type":"item","numeric-id":2214043,"id":"Q2214043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da8e8506e71d5bdd65012af9b409bee102160f86","datavalue":{"value":{"amount":"+0.7861371636390686","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":"Q6080370$F70DC8C3-070B-4581-9D02-1ADD3AE04C5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16108716ea2cc3d76b80a847fb1a524945ba6eb8","datavalue":{"value":{"entity-type":"item","numeric-id":4508618,"id":"Q4508618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d492d6a1a6bec03a9fd290c506d5da0ff7ebdf7e","datavalue":{"value":{"amount":"+0.7784969210624695","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":"Q6080370$CDFE9C2A-78A4-4BE9-B305-479F91CBC8A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e2542a2954db7849bc3dab3260457a78d6494ec","datavalue":{"value":{"entity-type":"item","numeric-id":1306425,"id":"Q1306425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1268bc74d30d3e162b5b63c93c0a31ed3f2896b5","datavalue":{"value":{"amount":"+0.7770168781280518","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":"Q6080370$DD437AF5-ACA4-478E-AF23-60B9C2CD002C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e0793774262369a44bfd33e10c786d21f136dfa","datavalue":{"value":{"entity-type":"item","numeric-id":1086587,"id":"Q1086587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca9740ce8174c7909639472b3963d3c683a3e2ea","datavalue":{"value":{"amount":"+0.775546669960022","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":"Q6080370$2870D9C4-5BB0-4F2A-B782-8EBCFD4C685E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6080370","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6080370"}}}}}