{"entities":{"Q5931908":{"pageid":8108710,"ns":120,"title":"Item:Q5931908","lastrevid":47608495,"modified":"2026-01-02T05:16:57Z","type":"item","id":"Q5931908","labels":{"en":{"language":"en","value":"On the elusiveness of Hamiltonian property"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1594648"}},"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":"Q5931908$D4D8E247-366F-4E7D-AA28-03987A3E647C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63bcb7309ec56d1d1ec3be1d480b3307c000ff02","datavalue":{"value":{"text":"On the elusiveness of Hamiltonian property","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5931908$52014AE6-5F63-468E-BE21-6DE40FC4A16B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1970e88f68fc37b669bced9c1b49744641904674","datavalue":{"value":"0979.05070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931908$EE974F48-854A-4490-A901-8FE2654E9C95","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d4b245ea79dd1faa9d4858129cce602a99bb2a28","datavalue":{"value":"10.1007/BF02669693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931908$F7B9BFBA-F51E-4E7D-A637-D1724BEE7C6B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4fc59f4567eafab16fdaccf0df8e89e49963298","datavalue":{"value":{"entity-type":"item","numeric-id":1578506,"id":"Q1578506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$154F25C7-F6EB-4E20-B5B5-808DC38E032E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bd8a7678534b4c4a434a737b8e34eefad997d7a4","datavalue":{"value":{"entity-type":"item","numeric-id":176689,"id":"Q176689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$731B6AA7-AFAD-400F-9A8F-B0DD32131289","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63e1d7063ecd638677848b844accef77290c7ea4","datavalue":{"value":{"time":"+2002-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5931908$3862711C-FA8A-4578-AB1C-C6BC35ED1661","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"029fffc7e35defb03ca626eb840450d97880c212","datavalue":{"value":"A graph property \\(P\\) on \\(n\\) vertices is a set of graphs on \\(n\\) vertices such that if a graph \\(G\\) belongs to \\(P\\) then any graph isomorphic to \\(G\\) is also in this set. Given the ability to make queries whether a desired pair of vertices of an input graph are adjacent or not, \\(P\\) is called elusive if it takes \\(n\\choose 2\\) queries in the worst case to determine whether a graph \\(G\\) is in \\(P\\). In 1973 Karp conjectured that every nontrivial monotone graph property is elusive. Even though it has been verified in special cases, e.g. by \\textit{J. Kahn, M. Saks} and \\textit{D. Sturtevant} [Combinatorica 4, 297-306 (1984; Zbl 0577.05061)] for graphs on a prime power number of vertices, in general the conjecture still remains open. The paper under review shows that the Hamiltonian property on \\(n\\) vertices is elusive in case \\(n=p+1\\), \\(pq\\) or \\(pq+1\\) for distinct primes \\(p\\) and \\(q\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931908$043F66E0-CE18-4EB0-BF46-5E49ECC4ECC9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c0617d45f23e5dfc7fb0eb4ddcab2f46301293e8","datavalue":{"value":{"entity-type":"item","numeric-id":414470,"id":"Q414470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$CFD99076-8F26-4436-A1B0-281A16DFAF52","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931908$0D094277-ACC8-4E40-8AA1-83264DF7CD4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931908$BF435574-E813-41F5-9748-852971C7ACC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931908$EAA4415C-7C24-4A85-A601-1320606119F6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e7991e623d616a23e0755c384cdb4d2ec4418844","datavalue":{"value":"1594648","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931908$1BB45A3A-6D92-4E6D-BD7F-702D2C2E44A7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75aad526b0a1b11d8b475e43283bfe0ad0b1e102","datavalue":{"value":"elusiveness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931908$8BAEBDA4-B205-4EEB-ACA3-A7F67527086B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3fa5c2f9ea10f7a980ffd84488ae2672a1a7a51","datavalue":{"value":"graph property","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931908$6BF76B2A-6484-46F5-BF0E-C688AAC98706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a5d5d1ee71b9902d8a5f4ed3cd858c2f4cf21c5","datavalue":{"value":"Hamiltonian property","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931908$D216EDB8-7DAF-4D87-905A-E90745692F87","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":"Q5931908$902D1F14-0642-4CD5-87D2-88DA53979768","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$31C4C1C9-C460-4002-913C-C0854ACB21EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7702836658cd393a9c33fb4e90fc2dd967a82b5b","datavalue":{"value":{"entity-type":"item","numeric-id":3715121,"id":"Q3715121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$03275A17-02F1-4D61-800C-55CDBCB6C077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c28903e6085f325f83f6c2f8674c9e4abb77407","datavalue":{"value":{"entity-type":"item","numeric-id":1065831,"id":"Q1065831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$8C2C8095-73EF-4591-9E18-01A035C8C666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5afd0476401b1c3ce6405b0e08cbff653c3ab4ae","datavalue":{"value":{"entity-type":"item","numeric-id":1212022,"id":"Q1212022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$F16ED0B7-7AF7-457B-9A2B-8F0286E231E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c985a1346de2fa98038bd505c44c7b1129deaf3","datavalue":{"value":{"entity-type":"item","numeric-id":1250227,"id":"Q1250227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$FBFBB234-CF7D-475E-AD70-6B77B017B81E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5baa038e2b83c96919ba9f894e301a3e1bfced95","datavalue":{"value":{"entity-type":"item","numeric-id":1578507,"id":"Q1578507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$425F5441-410E-46FA-80FD-7010116400EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"883ee85d25f75f7b450fed444fbf2c32a3433d35","datavalue":{"value":{"entity-type":"item","numeric-id":1960414,"id":"Q1960414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$D078AF8C-CD02-4C90-BC75-9C3DDDFD8670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dbb71381dc07ac06d1c435dcae76353158cb5fa","datavalue":{"value":{"entity-type":"item","numeric-id":1587333,"id":"Q1587333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$AD3F0AE2-B95B-4565-B4A1-035DBFF6E3DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a06aa0907bfece109c6170871d964a0c0b06afd4","datavalue":{"value":{"entity-type":"item","numeric-id":1176725,"id":"Q1176725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$AE3497EA-3234-4FB9-A1F3-6B916EB49762","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e008681d4aac72bdfed9ebec2d52c5051430fcba","datavalue":{"value":{"entity-type":"item","numeric-id":5641178,"id":"Q5641178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$CCDB1C4F-71CB-4989-9DEB-F5EF9AD74F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86bcdbb6b62740a718672bdb03490c1513e5dc50","datavalue":{"value":{"entity-type":"item","numeric-id":4131000,"id":"Q4131000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$CFA47005-85F6-4BE0-BAF9-505A53A101DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ada5e833849256e7c6c4ed899b4b7ff6538b0a3","datavalue":{"value":{"entity-type":"item","numeric-id":810043,"id":"Q810043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$992D5691-B497-44E9-B986-885A0EB9EAA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee426c17241539b87cf54f5e29134290ac95e674","datavalue":{"value":{"entity-type":"item","numeric-id":4181269,"id":"Q4181269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$78576D87-DBEF-4458-BEA0-5CD25B4AC114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63fa412b16fa1d1bf50cd43213a92001117a77bb","datavalue":{"value":{"entity-type":"item","numeric-id":3985804,"id":"Q3985804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$522C1A95-2B38-437F-8100-018E70659548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be7ec776afc6ad8ad178675a434e62027116713","datavalue":{"value":{"entity-type":"item","numeric-id":1238421,"id":"Q1238421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$815A5343-D824-420D-884F-26D3E9DE7F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb6635157d46ee699421ac79239513d8a4715c8c","datavalue":{"value":{"entity-type":"item","numeric-id":754889,"id":"Q754889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$2BA4FE52-71AF-40C6-8E31-16214118CBEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"967cfd82c02979daedba5432b2f7c61571fe301f","datavalue":{"value":{"entity-type":"item","numeric-id":4291554,"id":"Q4291554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$973415B7-47C3-4BC4-8AF6-297F9ECA1C49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d03e534d757ba7b288af1766b490e8ecb28c226","datavalue":{"value":{"entity-type":"item","numeric-id":1924495,"id":"Q1924495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$8A170083-3C19-49D5-AA9B-445AC3230140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cefcb0d68060735568a4211c0151369b4dfb2c05","datavalue":{"value":{"entity-type":"item","numeric-id":3792707,"id":"Q3792707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931908$605E4FD5-B032-43CA-986D-A4ADE0FA500D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f68ed7ddad97f6158793c4874149a2301439967a","datavalue":{"value":"https://doi.org/10.1007/bf02669693","type":"string"},"datatype":"url"},"type":"statement","id":"Q5931908$4520E888-B0C8-46C7-9899-9616C59C33B9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba8e6d5b358ec9e82fb0d7334d9cf5167afcbd6f","datavalue":{"value":"W2005852719","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931908$034CA42E-3FC6-431F-816F-0584CD1D30CA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91290f92153bed9ffbeb6b743b188a9534c4e5ae","datavalue":{"value":{"entity-type":"item","numeric-id":4651528,"id":"Q4651528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8301259851256cb99ecb51a982f7bc781e059f34","datavalue":{"value":{"amount":"+0.8283659219741821","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":"Q5931908$5A1901E3-032D-4ED8-A787-37E0C6D636F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53c401999652a460e3c45e78bcf3874d8cd37adc","datavalue":{"value":{"entity-type":"item","numeric-id":1587333,"id":"Q1587333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7058c93de03985f44f900c7f6b3d85ad4edc74de","datavalue":{"value":{"amount":"+0.8096029758453369","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":"Q5931908$B31A0628-A6EE-4010-AC6D-AD4C99D89977","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ff37e10963722c0911d0a9a80cc7fb523542065","datavalue":{"value":{"entity-type":"item","numeric-id":4291554,"id":"Q4291554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7af1df738e615da2ac1fa3888efe65b411cacdc2","datavalue":{"value":{"amount":"+0.8043537139892578","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":"Q5931908$1E4813B8-7232-4E7C-8094-35727A76D2F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64caae9ffa297c1d8033239e8d04a8df28b8e26f","datavalue":{"value":{"entity-type":"item","numeric-id":3344029,"id":"Q3344029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7686a6375cfcf43454c3ff80ab78ae52db19aa10","datavalue":{"value":{"amount":"+0.8042295575141907","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":"Q5931908$EDC5385F-4FAE-451E-83D5-BF1FA62452E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8077610e6faf8888d7f227c837c64e5fb0543eb7","datavalue":{"value":{"entity-type":"item","numeric-id":3680877,"id":"Q3680877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4f662486cf630173a8c8ad4e9d44b5fff70bb00","datavalue":{"value":{"amount":"+0.7926574349403381","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":"Q5931908$3882E261-2AF7-4882-852C-76AB03C06532","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5931908","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5931908"}}}}}