{"entities":{"Q2675842":{"pageid":2686585,"ns":120,"title":"Item:Q2675842","lastrevid":57973752,"modified":"2026-04-03T07:27:39Z","type":"item","id":"Q2675842","labels":{"en":{"language":"en","value":"A note on Hamiltonian cycles in 4-tough \\((P_2 \\cup KP_1)\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7592407"}},"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":"Q2675842$35D36BF0-73FA-4746-8946-FE033CE5F0AA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e2876c99013a5ee3ac9396c1c49d7fa0c5587aa8","datavalue":{"value":{"text":"A note on Hamiltonian cycles in 4-tough \\((P_2 \\cup KP_1)\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2675842$578D36C8-5F0C-4E1D-B65E-A6CDA8135A92","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d281b7b32cb14389f02c730f012ed8c2efede985","datavalue":{"value":"1506.05114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2675842$D6D2A23B-D6E3-4449-B275-C7F895A8E226","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dfaafb106f9a8d8ee91d04313777c0121c587b99","datavalue":{"value":{"entity-type":"item","numeric-id":2008446,"id":"Q2008446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$853BB2E2-B284-458A-B165-F34129509CF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f312e00acc1947270ff9dd670df2a632a917a4a3","datavalue":{"value":{"entity-type":"item","numeric-id":463283,"id":"Q463283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$BFB0E112-EBC9-463C-A25A-17E92ADFF707","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":"Q2675842$FE5B0702-6096-4DB1-9C32-042C6ACA7859","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9376c8de36d20cd151ffe6f1624817feab6592ab","datavalue":{"value":{"time":"+2022-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2675842$9CF5927E-FF82-45F5-9CA5-09100F090F17","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"804329cc7bee9f8ba9d490429d159b6cc0da4ee7","datavalue":{"value":"https://arxiv.org/abs/2202.06192","type":"string"},"datatype":"url"},"type":"statement","id":"Q2675842$11C2FD43-9CF2-4273-AD8F-0842B0A6D28D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f909b0c899eb5c99a72010a1ae51517b5b16fe82","datavalue":{"value":"A graph \\(G\\) is \\(t\\)-tough if for every cutset \\(S\\) of \\(G\\), the ratio of \\(|S|\\) to the number of components of \\(G-S\\) is at least \\(t\\). \\textit{V. Chv\u00e1tal}'s famous toughness conjecture [ibid. 5, 215--228 (1973; Zbl 0256.05122)], which is still open, states that there exists a constant \\(t_0\\) such that every \\(t_0\\)-tough graph is Hamiltonian.  There have been a lot of results verifying the conjecture for graphs in which certain small line forests (forests formed from the disjoint union of paths) are forbidden. One such kind of result is on \\((P_2 \\cup kP_1)\\)-free graphs. While there exist results for \\(k\\in \\{1,2,3\\}\\), the authors investigate the conjecture on \\((P_2 \\cup kP_1)\\)-free graphs with \\(k\\ge 4\\) and obtain general results in this paper. The main result is that for an integer \\(k\\ge 4\\), a \\(4\\)-tough and \\(2k\\)-connected \\((P_2 \\cup kP_1)\\)-free graph \\(G\\) is Hamiltonian. As a corollary, it is also proved that for an integer \\(k\\ge 4\\), every \\(k\\)-tough \\((P_2 \\cup kP_1)\\)-free graph on at least three vertices is Hamiltonian. The authors also pose a conjecture that the \\(4\\)-toughness condition in the main result can be reduced to \\(1\\)-toughness.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2675842$7717A61E-5FD4-4365-9C04-141C15037985","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2675842$2D47DCA6-6D39-4974-B84C-CFBB292E0209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2675842$43F4B6FC-D5BA-4D4F-8D56-0CBC874E48D9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5430362623d61bb7b910c1415b52d020c5545da4","datavalue":{"value":"7592407","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2675842$89BE2B1D-F808-485F-960F-3ECAF00A980F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09f50b21eea75ffdc199ef6f495164ba5c08bd0f","datavalue":{"value":"toughness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2675842$D702BA1D-6EE8-4F5D-A68A-C03A0F4B0142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2675842$BE96B356-8B48-472A-A30F-147C07C42D58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e81433387e2d674b0ffd173d7bf75dc89d812002","datavalue":{"value":"\\((P_2 \\cup k P_1)\\)-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2675842$F4B87ACE-D69C-489B-B1DD-8AC7A1CC7962","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1beb3b5523f065d236d4122f77352f31961a7fe3","datavalue":{"value":"Q114190479","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2675842$3120E2B6-751F-47BE-A49F-8F14494D1FC7","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":"Q2675842$039F3605-25B1-4BE4-9D63-9F08F85C5A68","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a77b34edb698f3e35e744d75f9903dc4f299d66c","datavalue":{"value":"W4285992051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2675842$010CDE65-4B7A-4BFC-B6E9-66E74C13EDD0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fd2f8cc1b4cd45120c37cc61ca7724a8c772a55","datavalue":{"value":{"entity-type":"item","numeric-id":1962051,"id":"Q1962051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$F114E506-B9BA-4400-BEF1-34E6DD3F72A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b09b1af166edf8069d8e0c8f23f9ff9cfe3f496","datavalue":{"value":{"entity-type":"item","numeric-id":2494126,"id":"Q2494126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$825403F2-5FD7-47C2-978A-966FE8A74F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"655c20e23fa51bcfbba6f11102f801010919fd08","datavalue":{"value":{"entity-type":"item","numeric-id":1894753,"id":"Q1894753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$1A475B68-C7BD-4419-A59A-4000FD761308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"888ac9f7db87ff471747cb61b3aec25f36fd97e9","datavalue":{"value":{"entity-type":"item","numeric-id":5417820,"id":"Q5417820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$F48497E4-F89A-4797-994E-61DFD110C726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2ca07d50aa240b4ccbe9fedf2b4516f9bba12f","datavalue":{"value":{"entity-type":"item","numeric-id":2558871,"id":"Q2558871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$453D30A5-F229-4489-A5F5-97B4BC8BA417","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":"Q2675842$50380912-77ED-4E86-B5C8-92B38E6F76D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$4DF6016F-766B-4B52-B392-D099F9A5E9D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1828366eaa2c4520e09ad2f3a10ff443952830cb","datavalue":{"value":{"entity-type":"item","numeric-id":339484,"id":"Q339484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$50A9A159-C06C-4BCB-A3C7-9FC39E71F14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9305221ae1c1a6d88e1779cf5dc8e96066d4a208","datavalue":{"value":{"entity-type":"item","numeric-id":5066893,"id":"Q5066893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$1E5EE18F-7B25-4576-81B6-C0B245FCFF68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf78c4274410291352778b4ab453c320fbc0e40","datavalue":{"value":{"entity-type":"item","numeric-id":2227834,"id":"Q2227834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2675842$E60E9B30-0E09-47D9-8E06-AE03EAB9AB24","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b43a1f546a2fc91b5f689be8085253e9f4b0d507","datavalue":{"value":"10.1016/J.DISC.2022.113081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2675842$E6ACF1C7-02F7-49EA-920A-FB756C88F43B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea41cca792224dcbf42d2143ede7ea5ff3c99cc3","datavalue":{"value":{"entity-type":"item","numeric-id":2062680,"id":"Q2062680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2381bd8e9c15c056f4c613f78373d35f7a3adccb","datavalue":{"value":{"amount":"+0.8594283","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$3A9AC13D-8E75-4A63-9DA9-3A7A91450499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ce7a441d865461f526ae34707f2bd4c6017834d","datavalue":{"value":{"entity-type":"item","numeric-id":2227834,"id":"Q2227834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae12471b707d752cf0132fabfef4ce0849a598e7","datavalue":{"value":{"amount":"+0.8543464","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$4DE9C7E9-FB0B-49B7-B763-2542D30DE2FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d53f3c5bbba81eda2c00ff0251e4ea981fbaba2e","datavalue":{"value":{"entity-type":"item","numeric-id":2045380,"id":"Q2045380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f64a825a2caa7287bc3c49b8f18f2b3e6070c864","datavalue":{"value":{"amount":"+0.83036286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$47D312D2-BE91-464D-A786-04C38FF3233E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc51dacf8ab601203fc046f904e4571f0a5cbbf6","datavalue":{"value":{"entity-type":"item","numeric-id":2675828,"id":"Q2675828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74b7c2ae5e5145caafca321f27036272a7011f51","datavalue":{"value":{"amount":"+0.830262","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$7CB83470-9073-4EF5-B69D-FB576568EEEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f767ceaea68bcfac6b78f4d92d551891a699b769","datavalue":{"value":{"entity-type":"item","numeric-id":339484,"id":"Q339484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0b7ce8176b3a173d299abaf013a2fb4a3d39f33","datavalue":{"value":{"amount":"+0.8300395","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$7DB3E49F-473B-4654-AE36-DF3E4C2BF7E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71e2afe15e0c6ae24bcdd903fca855dee69e0103","datavalue":{"value":{"entity-type":"item","numeric-id":5417820,"id":"Q5417820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a99e3cb9fd85ca9d402a12a8f3feebc524ababbf","datavalue":{"value":{"amount":"+0.81998616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$C573F8A0-43CF-4043-B5C9-27637E6D8869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a4fd4f7c2a13e4f34d3029cac913fc35b0b9e88","datavalue":{"value":{"entity-type":"item","numeric-id":1952726,"id":"Q1952726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"913a5e9d0318c7e9e480e9e7ed4a06edc21362df","datavalue":{"value":{"amount":"+0.80865306","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$607B4E6C-B2FC-4D69-8F4A-7EBB6A8BDFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3c27c16e81dfbcd6318c525661a6638a9314634","datavalue":{"value":{"entity-type":"item","numeric-id":2698533,"id":"Q2698533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cecf6102971416d35d95b96fb013f27af15281f","datavalue":{"value":{"amount":"+0.7966683","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$F309FF81-7F2A-4BCA-AE67-DBF8AD646498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0431764f696d9c24eaab21fcbd4da5a5060a194","datavalue":{"value":{"entity-type":"item","numeric-id":5066893,"id":"Q5066893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d63a5cae60582e599e2a7884c85c2e215b83744d","datavalue":{"value":{"amount":"+0.794398","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$B26E75C2-3F31-4600-985D-350123C7B03C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77e224312586d4131be11ff1bd85738988e58bc7","datavalue":{"value":{"entity-type":"item","numeric-id":6046653,"id":"Q6046653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ba92262d02b4432a0ecd108993836af9d8cabcf","datavalue":{"value":{"amount":"+0.7942532","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2675842$13C5849B-3239-4C6E-BAA8-12D67E3A00F7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2675842","badges":[]}}}}}