{"entities":{"Q1201257":{"pageid":1212006,"ns":120,"title":"Item:Q1201257","lastrevid":66861666,"modified":"2026-04-12T13:21:38Z","type":"item","id":"Q1201257","labels":{"en":{"language":"en","value":"Trahtenbrot-Zykov problem and NP-completeness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 97506"}},"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":"Q1201257$030C2D94-06F6-46B1-8A86-B24848FEB701","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"895c7dd3eeb7646a714fbb51e727215a7a384f7c","datavalue":{"value":{"text":"Trahtenbrot-Zykov problem and NP-completeness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1201257$F65A0633-B53D-40EC-8EBD-01C268E16CEE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9ab066d58d6445c7db541bc2134082c43b654845","datavalue":{"value":"0783.05076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201257$96A392C7-C82F-48B2-9A03-E60A38F879F2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a0965645fa0caa2546e8013e62827982c0e8a2fe","datavalue":{"value":"10.1016/0012-365X(92)90679-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201257$DF3A5501-7737-4476-9E3F-74476E11FDA2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa03cdb6cb01ae01d62ba8da3e11a6038befd3d0","datavalue":{"value":{"entity-type":"item","numeric-id":1201256,"id":"Q1201256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201257$7F88A35D-FD6F-4D76-B3FA-528BB80E8DD0","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":"Q1201257$AE5889DB-3C7D-4426-915A-7249A5C07206","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0879f591850b4f9f14b2c481d3e08995aa22089","datavalue":{"value":{"time":"+1993-01-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":"Q1201257$3BB5DB8D-8B70-4C14-9C53-C38817972E9E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"32bd9459cf1790d7a9f1a8a064dc40c80c8e56e1","datavalue":{"value":"The Trahtenbrot-Zykov problem for a class \\({\\mathcal L}\\) of graphs is the following: Given a finite graph \\(H \\in{\\mathcal L}\\) does there exist a (possibly infinite) graph \\(G\\) in which the neighbours of any vertex induce a graph isomorphic to \\(H\\)? For many simple families \\({\\mathcal L}\\), such as paths, cycles, subdivided stars, or star forests, it is known precisely which graphs \\(H\\) admit such a \\(G\\). The problem is known to be undecidable when \\({\\mathcal L}\\) is the class of all graphs, but decidable when \\({\\mathcal L}\\) is the class of all trees. The author constructs a class \\({\\mathcal L}\\) of graphs for which the problem is NP-complete. This is done by a clever construction which transforms the hamiltonian cycle problem in triangle-free cubic graphs to the Trahtenbrot-Zykov problem for a suitable family \\({\\mathcal L}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201257$5BA97630-DEE4-4748-8DA3-5511E866F8CA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cc7e193006699e29b5b5a77a1be6eeba002bc504","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201257$379903A2-FC26-4825-9E69-DEDE5BD95323","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201257$F7342EB3-FE1B-46DB-9719-866C4EFDD111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201257$4AC5400A-E5F2-4CB5-A81B-55FF61024CE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201257$D6204287-2C0A-4666-B156-21C149E07527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201257$8CA4524D-7DE0-4225-AA03-A69FB52F3551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201257$4E7CABC5-39AB-4B2F-A5F3-788F1E15BBAF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e4c5ee79a7ab4bd0ce55a23e970404c363cb8721","datavalue":{"value":"97506","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201257$E4377ADB-9CBB-401F-B689-981B274DD4AB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb1cb971f0fc4fc22846d2783886dfce262a99bb","datavalue":{"value":"graphs with given neighbourhoods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201257$0B8B027A-A267-4543-B665-B96F48A1C4AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43893d5d64746664e118f56a0c06a6724f1206d0","datavalue":{"value":"unsolvability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201257$70973FC8-9D89-4F0D-8208-409FFD92EB14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201257$1EE5074E-558F-47D8-BE13-A7C6A5E5D0D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20f4152a115c0c9cd8c056b24482145e44271d10","datavalue":{"value":"Trahtenbrot-Zykov problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201257$683EA750-9057-4230-A0C8-DD7B3370F64B","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":"Q1201257$250D3BA1-D201-422C-8117-E7B6D6C10ECA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"73085d6e0645e8dcdec25886d5a9a46a274fc84d","datavalue":{"value":{"entity-type":"item","numeric-id":4027150,"id":"Q4027150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201257$AD786B5B-317C-48E6-AD6C-A462469F386B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccda7454e7c95de9073b7a5e826c30499a185445","datavalue":{"value":{"entity-type":"item","numeric-id":4698091,"id":"Q4698091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201257$AE3EA578-49AF-4F8B-9CEA-3CA47DAECDB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1265e0a19f7123597244182a83797672f10549d","datavalue":{"value":{"entity-type":"item","numeric-id":1233874,"id":"Q1233874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201257$4F5C8E24-532F-4E13-8BAE-22B3F0463EF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7920396b032affbe95f5a2248b0bca2bcdc8ea10","datavalue":{"value":{"entity-type":"item","numeric-id":4200107,"id":"Q4200107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201257$498D7848-0534-4E8C-928B-934CD764B334","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a64f2032be61bad2668ad77728b73313829a02d8","datavalue":{"value":{"entity-type":"item","numeric-id":1179032,"id":"Q1179032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e498b2f954046de3e9be49c71a0bb94cde0a10b8","datavalue":{"value":{"amount":"+0.7601099014282227","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":"Q1201257$FDF80375-7E0A-4DFE-B06C-55702CA17694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"672604bd9f28d08ddeac17d2325e9e4bcb7d96e0","datavalue":{"value":{"entity-type":"item","numeric-id":3201758,"id":"Q3201758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfd8b96d6b521054518b271f19b6b80af420dbf9","datavalue":{"value":{"amount":"+0.7530983686447144","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":"Q1201257$A876A807-928A-484E-8BF1-B1A6172D20EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"516a09b33704f9da8246ae1bb9b2901eedaa8eec","datavalue":{"value":{"entity-type":"item","numeric-id":4027150,"id":"Q4027150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d3dc2f0c92136c39bdc3f8b4508cff8095021a3","datavalue":{"value":{"amount":"+0.7529473900794983","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":"Q1201257$A10C3DED-822D-4D69-8506-052DDB4E7FB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c6e366815f469231b4e2a87bbedb8b0f73a9d96","datavalue":{"value":{"entity-type":"item","numeric-id":673092,"id":"Q673092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1474e43f77bd123f481bf76268082db94c599124","datavalue":{"value":{"amount":"+0.7497706413269043","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":"Q1201257$C1DF4B6A-EAD1-4AE0-B3C8-9D71031A173E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89dacd94fc24813bd4cf458d3d0cd2cdc474ef5c","datavalue":{"value":{"entity-type":"item","numeric-id":1356685,"id":"Q1356685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f2b9b3d50becf41e9077688aac85711123354ff","datavalue":{"value":{"amount":"+0.7467836737632751","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":"Q1201257$DFFC6A10-831B-4BEE-A0A7-94BA7248876A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Trahtenbrot-Zykov problem and NP-completeness","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Trahtenbrot-Zykov_problem_and_NP-completeness"}}}}}