{"entities":{"Q1962051":{"pageid":1972793,"ns":120,"title":"Item:Q1962051","lastrevid":47437300,"modified":"2026-01-01T18:17:03Z","type":"item","id":"Q1962051","labels":{"en":{"language":"en","value":"Not every 2-tough graph is Hamiltonian"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1395019"}},"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":"Q1962051$BB3B51D4-C5A1-456A-9CD5-42C30C108ADB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a5d6a6a46a04b8d9b5eb71761a165204586b989","datavalue":{"value":{"text":"Not every 2-tough graph is Hamiltonian","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962051$EFC905AD-6F87-4B1E-BC8B-7BD9A0B4F3EB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af9a9b5db6374e93a08874765b6c57dc0818c73f","datavalue":{"value":"0934.05083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962051$7E13885A-FBBC-43CF-AFAA-0CD6035EFFC1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7b6b3a0d419e150f0b7d4a1aed6585304596798c","datavalue":{"value":"10.1016/S0166-218X(99)00141-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962051$327FD28A-0A37-4383-8921-1D421C1C29EC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60ae56b79890118017fdfa61d163ccabbb05d00b","datavalue":{"value":{"entity-type":"item","numeric-id":585220,"id":"Q585220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$77C7C751-EC81-4050-AE59-194FCCF23E63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c15cd32c54abc58fde12b9b90b6f282b53cb3156","datavalue":{"value":{"entity-type":"item","numeric-id":339483,"id":"Q339483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$6630844F-3015-404D-874E-3C0F8EA479B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"098e4ad9b9b171d26caa4b6845dc27c4a8d71de7","datavalue":{"value":{"entity-type":"item","numeric-id":1363685,"id":"Q1363685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$E2535FC9-88E6-4213-9123-53512A1B2FF6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$FD423800-8D48-4D77-8E71-F8E915930ABC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3d7fcc00a8ca0e7d2bba3b2e6904026043bd3d23","datavalue":{"value":{"time":"+2000-04-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1962051$12C0EF64-36F1-4EAB-8F77-A07B658DFE8A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a379fe561c77ee6a50da5cabf9a74e22a9884b45","datavalue":{"value":"A long standing conjecture due to V. Chv\u00e1tal was that any \\(2\\)-tough graph is Hamiltonian. A very clever example is presented that disproves this conjecture. More specifically, it is shown for any \\(\\epsilon > 0\\), there is a \\((9/4 - \\epsilon)\\)-tough graph that does not contain a Hamiltonian path. In lack manner a \\((7/4 - \\epsilon)\\)-tough chordal graph that has no Hamiltonian path is presented. The latter result gives a lower bound to the toughness that will imply Hamiltonian in chordal graphs as opposed to the upper bound of \\(18\\) of \\textit{G. Chen, M. S. Jacobson, A. K\u00e9zdy} and \\textit{J. E. Lehel} [Networks 31, No. 1, 29-38 (1998; Zbl 0894.90150)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962051$0152CA8C-1C40-4971-A563-4BE26302ECC0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962051$A341CD10-FD4B-402F-AF6C-4F3FA29A74C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962051$45E4F399-4BC2-4D90-9945-7152818242B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962051$28D63982-0B3E-4273-8ADA-88A189B5D9B3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"652c768eea9a0ac2577e6f41901141d90550dc93","datavalue":{"value":"1395019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962051$6237F488-BBC0-400D-BFA6-9656BF537AC7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c822c54638e4070b56aee42666fe01efcdddece8","datavalue":{"value":"Hamiltonian","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962051$5033C22F-ED03-4C8B-842B-EEE634835893","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdd0b3d744bf8a2f260a2dd050fb6bbabe95ca41","datavalue":{"value":"tough","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962051$399A9BDE-AD61-48FE-BFBE-847EF4FF7E1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbad8d82eb60d0613d855047c74c19c0a727d34c","datavalue":{"value":"\\(2\\)-tough","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962051$8D272070-C64B-4BC2-BA4C-47A4706B4C85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"850f61d959a6d8fb5992794412d07f153ca78e39","datavalue":{"value":"chordal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962051$C63C2A80-14A4-4A60-88BF-2942285083DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b192458bf3e522f8d2259357613260c470fc9a0","datavalue":{"value":"traceable","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962051$2F407486-CFD0-4A5F-B5F0-A23D3267E8CC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"69ba710ec323ba2b1e2239c5bdd6e4165b935d93","datavalue":{"value":{"entity-type":"item","numeric-id":175582,"id":"Q175582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$B3A1916E-6B9A-47C8-BB35-AF17F332EB34","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":"Q1962051$37C72F3D-921F-4FFD-A7A3-F19FB9A1FF6E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3d694e90b514a5f22d8c550d030cdd224baa5660","datavalue":{"value":"Q29037944","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962051$2EFAC5C5-4C81-4201-B5B3-3BADA51F6EF7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2821cd57d893e0d97146d0ac1d9a53865edffa0","datavalue":{"value":{"entity-type":"item","numeric-id":4309982,"id":"Q4309982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$0849F975-E917-4CE6-BACB-BE24E246CA00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8776e2c2687519246d0fcbd44f52e65bb5dd3521","datavalue":{"value":{"entity-type":"item","numeric-id":1962052,"id":"Q1962052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$E82EBFF5-466B-4CBF-9807-E14DA7A5675A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba317c2146f6a5c380b7bc49ee4595b399d87ef0","datavalue":{"value":{"entity-type":"item","numeric-id":4290577,"id":"Q4290577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$ADBC183E-3325-4952-A688-02BB2F5F1FBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"884e45af458f02193c03ec9af9f7b2ed8879b357","datavalue":{"value":{"entity-type":"item","numeric-id":3866156,"id":"Q3866156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$5DBF4125-41B4-4279-A522-A30745884D36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$4D57D552-CEC0-40FD-9545-FE2B461930C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"004423741c39355f31866fbc3c137acae43555bd","datavalue":{"value":{"entity-type":"item","numeric-id":4378526,"id":"Q4378526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$4E969752-C219-4998-A928-52817583E776","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":"Q1962051$B9782252-AD7F-4FB6-9D52-4A6BC9453B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8788f05ae82cfbd0ae01fb3681f4ca02a719c218","datavalue":{"value":{"entity-type":"item","numeric-id":3731636,"id":"Q3731636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962051$3AF84352-0E6F-4B57-88F3-79A1AA61ACAE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b269698482b4724eead00ffc44de940839452ce","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00141-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1962051$A1484BAB-6363-47F9-892C-5DC9221081D8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c55097114804425e99f53a0a88790c1aadd3f12e","datavalue":{"value":"W2007167081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962051$34453ED0-3E12-4EED-B072-3E32CCB14ECD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90a1e4ddace039761cf4d52626cf6bdb72772a3d","datavalue":{"value":{"entity-type":"item","numeric-id":4309982,"id":"Q4309982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95f7a0557ad42fca1da77baf812f36f7914d6cba","datavalue":{"value":{"amount":"+0.8720231056213379","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":"Q1962051$68D5EFFF-E274-48B7-8D2D-0B3F276FBFD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"385ffe032c9e1d6a062a128ac47de177ccc7d0ee","datavalue":{"value":{"entity-type":"item","numeric-id":2558871,"id":"Q2558871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be432bfd2d9630347818c9ed5f86254548ef6ae0","datavalue":{"value":{"amount":"+0.8469823598861694","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":"Q1962051$4847573A-6CE8-4281-9CF8-420F5B9B3D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54fbe05a6a06f855e8a9ff6a27b59874aecfc530","datavalue":{"value":{"entity-type":"item","numeric-id":2675842,"id":"Q2675842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fda1b185c0b410bde4aba70a2f7882670275ff7","datavalue":{"value":{"amount":"+0.834412693977356","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":"Q1962051$EDC9C5C0-C3AB-4393-932B-16F375B96A1A","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":"1a5ab40adeca5788187319bd1fea1fda4e743085","datavalue":{"value":{"amount":"+0.8330898880958557","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":"Q1962051$65D25F43-ED30-4EBF-B23B-713557D2C173","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":"7015ee8a844d3f90f080b3180b976b5b6cb4a024","datavalue":{"value":{"amount":"+0.8291293978691101","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":"Q1962051$FAD4063A-C081-44D8-90B0-A61F4E4F6890","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962051","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962051"}}}}}