{"entities":{"Q1743684":{"pageid":1754426,"ns":120,"title":"Item:Q1743684","lastrevid":73602129,"modified":"2026-04-14T16:36:49Z","type":"item","id":"Q1743684","labels":{"en":{"language":"en","value":"Minimal \\(k\\)-connected non-Hamiltonian graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6859817"}},"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":"Q1743684$4FFDE288-3812-4756-AA9E-D5A167351EF7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34f232d0f73c5c86998453e7424bf5cce56306b0","datavalue":{"value":{"text":"Minimal \\(k\\)-connected non-Hamiltonian graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1743684$65196FCB-7279-4521-B997-997606D3C4EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f2adb549f61e74f9323de1373155bd0de9a2286c","datavalue":{"value":"1405.05095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743684$4EB87845-1737-4B9B-BA2B-F02F695F21E3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84b3ed84bea0d94201a16bb2ea3c8899c4642452","datavalue":{"value":{"entity-type":"item","numeric-id":281609,"id":"Q281609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$EC00410C-A026-4DCF-AF8B-CE8A4D26B9E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b839e7c32a4c3b2ef4f27fdd9abe0a56bb42f7dd","datavalue":{"value":{"entity-type":"item","numeric-id":251509,"id":"Q251509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$71CE0084-D9D4-4357-946B-D3E1F78AC174","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$9832EA42-3E36-4164-8E55-7A0D49419DF0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"30b43d2fa1cf1a5be87fe107e165135cb84cc159","datavalue":{"value":{"time":"+2018-04-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1743684$2ED25D3C-7064-40A0-87E6-72C1AF4F5690","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7050151be28b23e3534d23bc2bfb3b8fed860a0a","datavalue":{"value":"The paper explores the following general problem: what are the minimal \\(k\\)-connected non-Hamiltonian graphs? What is interesting here is that we can have various definitions for minimality. While a graph is minimal if it does not contain a smaller graph with the same properties, there are many different possibilities: one graph can be contained in another, say subgraphs, induced subgraphs, minors, and induced minors.  The paper discusses the problem for \\(k\\in \\{2,3\\}\\) with respect to the four containment relations mentioned above.   For \\(k=2\\), when the containment relation is minor, the problem is solved and the only minimal graph is \\(K_{2,3}\\). When the containment relation is subgraph, the problem is also solved and the minimal graphs are \\(\\theta_{a,b,c}\\) for \\(a, b, c\\geq 2\\) where \\(\\theta_{a,b,c}\\) is a theta graph consisting of two distinct vertices and three internally-disjoint paths between them of lengths \\(a\\), \\(b\\) and \\(c\\). When the containment relation is an induced subgraph, \\textit{J. Brousek} [Discrete Math. 191, No. 1--3, 57--64 (1998; Zbl 0958.05086)] obtained a solution for claw-free graphs.  In this paper, the authors contribute with a solution for the problem when the containment relation is an induced minor, where the minimal graphs in this sense are \\(K_{2,3}\\) and \\(K_{2,3}^+\\), which is obtained from \\(K_{2,3}\\) by adding an edge between the two vertices of degree \\(3\\).  For \\(k = 3\\), the authors conjectured a set of minimal non-Hamiltonian graphs for the minor relation and they prove one case of this conjecture, that is, every non-Hamiltonian planar triangulation contains the Herschel graph as a minor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743684$1F1AEE7E-7C55-4147-A4B4-AC6743B79F1F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743684$B6BC2EA8-CC96-4E61-9BEF-4E30FFA1B1BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743684$6C775C3D-2A95-477D-9651-F5C9E0D7B81E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1934f7ed94d90b8915ae63a5d77b547673652207","datavalue":{"value":"6859817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743684$F89E9356-AC1F-4D26-AD7E-CF13940AF97D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c51a5f2b554ad725199c724ddbac3b61a9fd8af1","datavalue":{"value":"Hamilton cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743684$B38247DF-4B68-457F-AA05-1DF5728D60F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b4a7e94f67b1256fa87c9c444c77ea9a3d63a5","datavalue":{"value":"graph minors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1743684$15A94FC0-4484-4125-AD2D-42308ACAA2D6","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":"Q1743684$FAC9E424-718E-4929-AD8B-BD89E56D3AB1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a3d29539b81d6f2ece291076b45a1a7b0c33ff76","datavalue":{"value":"https://doi.org/10.1007/s00373-018-1874-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q1743684$2EF1FAA1-C345-4475-82E7-90CA3EC7203C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"158d8a4728b7dde81b10eaabd8adf30ab70fbb4e","datavalue":{"value":"W2793974272","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743684$C656AF82-2F65-4AB7-8CE1-6A37C1BBE60E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"643906894f9f1a4a78a5bd85d9f0d75a60c4c5a5","datavalue":{"value":{"entity-type":"item","numeric-id":3465653,"id":"Q3465653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$4381CBC9-8151-4B9B-B487-A982C4F47CEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4907ca4c057393c96304d3d4520f0db81db894bb","datavalue":{"value":{"entity-type":"item","numeric-id":1584413,"id":"Q1584413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$EC24F138-0542-4799-AAB6-F7551A10BA96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f993fa3be11c6391db22af264d900e0243f8cb60","datavalue":{"value":{"entity-type":"item","numeric-id":1931398,"id":"Q1931398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$4E5FA8D2-A6A2-46BC-864C-8CA8C03F9100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86ee4b5aec7c57f1369b27ad508e8d6185d4489d","datavalue":{"value":{"entity-type":"item","numeric-id":2551113,"id":"Q2551113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$89D40369-0ABC-4EA3-A969-10970EB992FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1333f52920ad80dcb5910bfdb9960ef694b62218","datavalue":{"value":{"entity-type":"item","numeric-id":4632017,"id":"Q4632017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$7B491340-1468-4294-BC70-06B1025AB611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53c7fa8527913cb78fd2fe3a1821ffe47bdefc87","datavalue":{"value":{"entity-type":"item","numeric-id":4798110,"id":"Q4798110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$E68B521A-CE89-4DE1-809D-30CEB5B94011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"635cac23ef0782866b32355016d2c79a25301774","datavalue":{"value":{"entity-type":"item","numeric-id":5597451,"id":"Q5597451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$8252D40A-88FD-4C38-8795-B275CA9571A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e194522202c0cc2891b8b360424121f29114928","datavalue":{"value":{"entity-type":"item","numeric-id":1813957,"id":"Q1813957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$D7D8B48F-58D1-4274-8787-2C69DF77D653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62d035f421ab9bd8eaa29b517b29669cf50cb87e","datavalue":{"value":{"entity-type":"item","numeric-id":1144028,"id":"Q1144028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$FB0FEDF3-BDD1-4488-8703-BF9FC7189B91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e433882c660a8e8d06ac4719241565d5c33a0d4b","datavalue":{"value":{"entity-type":"item","numeric-id":3231816,"id":"Q3231816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1743684$D34CD730-1AC7-4EAA-ACCA-291A21B70139","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"39adfc8b0aabc5582dffaae90d56c1a295eb840f","datavalue":{"value":"10.1007/S00373-018-1874-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1743684$F37F54A8-2D27-41C9-9FE2-C84B136874BA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22e9bff678f7cbdaefc46b79e237f98732f8a160","datavalue":{"value":{"entity-type":"item","numeric-id":1584413,"id":"Q1584413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a03e64f38e4cf6f7880cb5a1e7b0e0d33fff0db","datavalue":{"value":{"amount":"+0.8289243578910828","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":"Q1743684$519B160E-206E-4D6D-A368-8DD2B93C421B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dc6d2edf2bd541dcd8ec64790d551d181b81c04","datavalue":{"value":{"entity-type":"item","numeric-id":2138961,"id":"Q2138961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72a72f597815c5ce66844d1ba4d27399a9f66cbe","datavalue":{"value":{"amount":"+0.8070840835571289","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":"Q1743684$843917E5-6EAF-4DF9-81B9-E8BB42D785DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f277368a934a3e989942fde5490509f8f7d989f4","datavalue":{"value":{"entity-type":"item","numeric-id":4632017,"id":"Q4632017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3803809b5c369684e9e725be488979f8aca8abb","datavalue":{"value":{"amount":"+0.774739146232605","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":"Q1743684$377EC6ED-F625-4827-AA8A-D5D17FEF28D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcf4c40bf43bcd252a302695040323c4ae2c4873","datavalue":{"value":{"entity-type":"item","numeric-id":4213895,"id":"Q4213895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ace6f7fb1efd8c460fc332e5179951cb2f803a6","datavalue":{"value":{"amount":"+0.7674136757850647","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":"Q1743684$73514094-E056-4426-89E8-2364F575747B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ead7b38c9f9fcd38fb9d38a83fa252ad9ff6b333","datavalue":{"value":{"entity-type":"item","numeric-id":4539874,"id":"Q4539874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f293428673c8b6b8928685e964e41ba2c74aba2b","datavalue":{"value":{"amount":"+0.7630547881126404","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":"Q1743684$FDD39BDF-D2BB-479F-ACB6-E468E2A12240","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimal \\(k\\)-connected non-Hamiltonian graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimal_%5C(k%5C)-connected_non-Hamiltonian_graphs"}}}}}