{"entities":{"Q7231827":{"pageid":24492512,"ns":120,"title":"Item:Q7231827","lastrevid":84475781,"modified":"2026-05-18T15:26:09Z","type":"item","id":"Q7231827","labels":{"en":{"language":"en","value":"Every 4-connected \\{claw, hourglass\\}-free graph is 2-Hamiltonian"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8189165"}},"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":"Q7231827$BAA0DA36-9994-47EB-BAE5-C1841676F217","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7fb5ab6a56e681986a4e646a9c8de7e9d2664b65","datavalue":{"value":{"text":"Every 4-connected \\{claw, hourglass\\}-free graph is 2-Hamiltonian","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7231827$D270D9ED-0AED-45B9-9D6B-437790535AA9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dcbe800503edfab6e1fa3cfc55a58eb3d616ddab","datavalue":{"value":"10.1016/J.DISC.2026.115073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7231827$40D07C8D-E9C2-44BC-AF69-C66CAB900192","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c55b4256f86b98171d4f748484e64112c021021","datavalue":{"value":{"entity-type":"item","numeric-id":186096,"id":"Q186096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$C74F4B06-19E1-4A59-98A6-70442C86CF62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a968f932e0d6c1f5b807a52c24894ae22ef59d0","datavalue":{"value":{"entity-type":"item","numeric-id":297931,"id":"Q297931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$FB4E3D1A-63B2-475B-9806-EE8DC875FF79","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$5F4E69AF-6F4C-4033-9C72-8DE9AB0CCE44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"22b7db1ee47288e2a17e9877aecc2cd5315e6862","datavalue":{"value":{"time":"+2026-04-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7231827$60A05AA6-6311-41FA-9612-8A4874D0A712","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8581f8702856cac22247af91179a3685a73986a1","datavalue":{"value":"For an integer \\(s\\ge0\\), a graph \\(G(V,E)\\) is \\(s\\)-Hamiltonian if, for any \\(s\\)-subset \\(X\\subseteq V\\), \\(G-X\\) is Hamiltonian; an alternative definition is discussed in \\S2 of the paper. \\(\\Gamma\\), the hourglass, is the unique 5-vertex graph with degree sequence \\(4,2,2,2,2\\) -- this is the graph the authors called \\(\\Gamma_0\\) in their paper (jointly with other authors) [\\textit{A. Kabela} et al., Discrete Math. 348, No. 2, Article ID 114305, 19 p. (2025; Zbl 1553.05100)]; the claw is \\(K_{1,3}\\). \\(G\\) is \\(\\{K_{1,3},\\Gamma\\}\\)-free if it contains neither of the two ``forbidden'' subgraphs as an induced subgraph. The main result of this paper is Theorem 1: Let \\(s\\ge2\\) be an integer, and let \\(G\\) be an \\((s+2)\\)-connected \\(\\{K_{1,3},\\Gamma\\}\\)-free graph. Then \\(G\\) is \\(s\\)-Hamiltonian. This theorem is proved by induction on \\(s\\), beginning with the titular theorem, Theorem 2, which is the case \\(s=2\\). A consequence of Theorem 1 is Corollary 3: (i) Let \\(s\\ge2\\) be an integer, and let \\(G\\) be a \\(\\left\\{K_{1,3},\\Gamma\\right\\}\\)-free graph. Then \\(G\\) is \\(s\\)-Hamiltonian if and only if \\(G\\) is \\((s+2)\\)-connected. (ii) For an integer \\(s\\ge2\\), \\(s\\)-Hamiltonicity is polynomial-time decidable in the class of \\(\\{K_{1,3},\\Gamma\\}\\)-free graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7231827$D6F02FAF-6E6A-44AF-9251-C27844E5C070","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$ABE9AA46-6E70-41F0-9D03-FAE3D74DF899","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7231827$4A2C8999-03F4-4A01-BE2A-2D1303C6498B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7231827$DDAE5561-D362-4F06-A969-DFB27805A1F2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"93c6601b0f880b2a1e6afb236b031528f3861235","datavalue":{"value":"8189165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7231827$B3561967-6B46-4718-AFDB-0E4358ACCB39","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d157ee1b6cb38f19194c40d185fb66fde321d54f","datavalue":{"value":"2-Hamiltonian","type":"string"},"datatype":"string"},"type":"statement","id":"Q7231827$6B0BA19F-4563-45A8-ADB7-A627A4120032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2955d3dde9a15e46dba801e05da2cd70a0c42a19","datavalue":{"value":"closure","type":"string"},"datatype":"string"},"type":"statement","id":"Q7231827$DECE81AB-4EB9-49AE-901B-DB5A6349198A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1db4e3cd8c6237e3b25098b483a3ff821c3b321","datavalue":{"value":"forbidden subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q7231827$31690AB6-9FF4-4D05-B102-3E2E1BE8383E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5afaa21ea39052b2c43f5f2a349f6e3232c702cd","datavalue":{"value":"claw-free","type":"string"},"datatype":"string"},"type":"statement","id":"Q7231827$6C1DB3BA-4DDC-45F9-85AA-BA18EA900FF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a3504ca51ef061f30824f2521b1786e9938037e","datavalue":{"value":"hourglass-free","type":"string"},"datatype":"string"},"type":"statement","id":"Q7231827$5148AFFC-D4CB-489A-A9B7-C7C4C0DB5CA6","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":"Q7231827$E67F6FB3-AFB4-4A82-A2FD-4A01666E6122","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$923A0913-D933-471D-A897-E32D9048B00D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd315a4856a894081bf7ff25366e47cb19e0b854","datavalue":{"value":{"entity-type":"item","numeric-id":1297424,"id":"Q1297424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$6B06B9CB-1A0D-4269-925E-3AF958AC108F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc7cfe6d6660bed1830c41d9e3eb20806b8de25d","datavalue":{"value":{"entity-type":"item","numeric-id":1292819,"id":"Q1292819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$79D445BA-52D6-4B0D-B34D-8C7304D7CF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64297ae8a0e36a6a2e4046b8c9ea88b84910950b","datavalue":{"value":{"entity-type":"item","numeric-id":3808126,"id":"Q3808126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$30C8CBDD-767B-4E77-95F5-57A6154CBE73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42023445f19cb3ec8b66ba61176c43ad29c36acf","datavalue":{"value":{"entity-type":"item","numeric-id":1126285,"id":"Q1126285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$00003F83-9116-497E-91B7-C24D3E7DCB3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0309e233da74513be4fb15dad37b6e4bd3b8e71c","datavalue":{"value":{"entity-type":"item","numeric-id":1011773,"id":"Q1011773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$86599370-38B9-400F-A407-99351EAF1AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78142425e57f895e472d8c08743c5cc9791af2e9","datavalue":{"value":{"entity-type":"item","numeric-id":5509542,"id":"Q5509542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$13AC490C-C7C0-458A-9786-0DD7587E1792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0080f371dde68bce61027fd3890afb169db382ab","datavalue":{"value":{"entity-type":"item","numeric-id":394533,"id":"Q394533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$DCDC6505-E0D6-4F6F-AE85-DD6C7A4248F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7cc7ef8790a58c0605088145768f82426b78211","datavalue":{"value":{"entity-type":"item","numeric-id":5837982,"id":"Q5837982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$A3278927-EA3A-4DE9-936A-CCD80CD7B749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7363ea36466e05a1563486052c8141b433be97f0","datavalue":{"value":{"entity-type":"item","numeric-id":3320427,"id":"Q3320427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$C1082553-1A20-4CF7-8CE7-7118636E9A9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"084617817f9782a5f548a1325e578c0f5d735267","datavalue":{"value":{"entity-type":"item","numeric-id":2852612,"id":"Q2852612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$72BBD14E-606F-423C-BB37-F2544B3FD462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c88e1207a0d8e08dfaf8023fc48ce90580a907e6","datavalue":{"value":{"entity-type":"item","numeric-id":1362093,"id":"Q1362093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$8B09D43E-FFA2-4265-AB1C-4C33E8DF73F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"616f8cad445076a343a7a270a27ddeee4405fecf","datavalue":{"value":{"entity-type":"item","numeric-id":4808405,"id":"Q4808405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$49473FEB-25F7-446A-96A0-73D0CEEE61DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b4a71fa9a3529a264c0cb20a6c0756e8a4bd8a5","datavalue":{"value":{"entity-type":"item","numeric-id":3081311,"id":"Q3081311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$FA56CE33-6F25-47F6-A364-3939C1A353CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c541e009df656fc6e7412ca901fd24cf23cdf4a8","datavalue":{"value":{"entity-type":"item","numeric-id":1744769,"id":"Q1744769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$1FFCFE3C-41E1-48AC-8A75-FC00384985FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc5f3aa6709c8e05f41c54e6b178bf084b8cf312","datavalue":{"value":{"entity-type":"item","numeric-id":4722106,"id":"Q4722106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$AB15D54B-CAC3-43CD-A319-AFBE83250A90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ebf5dcdf9b1fcdea0b5fcf5e4c8a029eb0b3e8d","datavalue":{"value":{"entity-type":"item","numeric-id":2142636,"id":"Q2142636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7231827$F8CFB624-1296-4B48-8A31-C29C9FFB3943","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:7231827","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:7231827"}}}}}