{"entities":{"Q512653":{"pageid":514420,"ns":120,"title":"Item:Q512653","lastrevid":62397069,"modified":"2026-04-11T05:48:28Z","type":"item","id":"Q512653","labels":{"en":{"language":"en","value":"Generalized Gray codes with prescribed ends"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6689525"}},"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":"Q512653$CF631B2B-06D0-4837-94E3-B3D3624F9056","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"117e058edabe4a611d7ee67ee3dcee1b6ba4d140","datavalue":{"value":{"text":"Generalized Gray codes with prescribed ends","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q512653$2E72F619-14CE-4094-BF57-5D8741CD6602","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f4762c9f287515e22b762e2cfe8238280d014df","datavalue":{"value":"1367.94402","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512653$32092CAE-94B9-4A4F-A2C0-FF5A5CDCA731","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"43c1544eb580d9f9be984f2dd17d8b2cd8015b4f","datavalue":{"value":{"entity-type":"item","numeric-id":414470,"id":"Q414470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$85493215-15E8-4BC5-A73A-B7D61EC8F375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7371863d74d7748be96f842909a66fecfc2118d9","datavalue":{"value":{"entity-type":"item","numeric-id":313800,"id":"Q313800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$491BFBCE-7E33-4FCE-B638-B4647D7F99BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"764f84a646c763434432ad369d0bc1a8abdf96a9","datavalue":{"value":{"entity-type":"item","numeric-id":409252,"id":"Q409252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$4F7A0922-FFB6-46A8-8F90-B921F7366BA1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$09863852-DE3A-4E36-B3E2-567992A9E69B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"239465d3f72b1d0ceb374a3180654de1deb818a8","datavalue":{"value":{"time":"+2017-02-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q512653$08FB1C3D-F942-4ADD-9F59-96C2CD26C225","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5acaa4ff100b45e42011f9af29fb655c220bfba1","datavalue":{"value":"https://arxiv.org/abs/1603.08827","type":"string"},"datatype":"url"},"type":"statement","id":"Q512653$FCEC0F58-B92F-4D8E-8E39-3D0A67163F10","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a9b50d1693f52f2e55e4a722a7e750d42addafd6","datavalue":{"value":"An \\(n\\)-bit Gray code is a sequence of all \\(n\\)-bit vectors such that consecutive vectors differ in a single bit. Given any two \\(n\\)-bit vectors \\(\\alpha\\) and \\(\\beta\\), there is a Gray code starting in \\(\\alpha\\) and ending in \\(\\beta\\) if and only if the Hamming distance \\(d(\\alpha,\\beta)\\) is odd; see [\\textit{I. Havel}, \u010cas. P\u011bstov\u00e1n\u00ed Mat. 109, 135--152 (1984; Zbl 0544.05057)]  \\textit{R. Caha} and \\textit{V. Koubek} [Discrete Math. 307, 2053--2066 (2007; Zbl 1125.05054)] generalised this fact by defining any set of \\(2k\\) distinct \\(n\\)-bit vectors \\(\\alpha_1,\\beta_1,\\ldots,\\alpha_k,\\beta_k\\) to be \\textit{connectable} if there are \\(k\\) sequences of distinct \\(n\\)-bit vectors that partition the set of all \\(n\\)-bit vectors such that, for each \\(i=1,\\ldots,k\\), the \\(i\\)th sequence leads from \\(\\alpha_i\\) to \\(\\beta_i\\) and its consecutive vectors differ in a single bit. Caha and Koubek proved that, for \\(k\\leq n/2\\), each such set of \\(k\\) vectors is connectable exactly when \\(d(\\alpha_i,\\beta_i)\\) is odd for each \\(i=1,\\ldots,k\\).  The present authors improve this result by proving that it is also true more generally when \\(k\\leq n-1\\). This is a best possible bound and improves previous partial improvements in the literature.","type":"string"},"datatype":"string"},"type":"statement","id":"Q512653$A436E88C-8672-4EBB-BD72-C77CBD170C5E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4b6daa67a0e42b208d8b116bb9a44ab2f9a975bd","datavalue":{"value":{"entity-type":"item","numeric-id":189835,"id":"Q189835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$2F8F69A2-FB32-44DB-B62B-111E6B9B5BBB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c3cdafa68da1cd8441c02cae1d4f7b344a92c14","datavalue":{"value":"94B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512653$373D4499-EE06-4B6B-B229-621125574832","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"36ba6463389b7a9e66a8807c384cba9bc5963272","datavalue":{"value":"6689525","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512653$C3642FE5-83E0-44FF-AB3A-E71582E1B58B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa8a30ad74939d539f91080a0dfdc10278d4afb1","datavalue":{"value":"Gray code","type":"string"},"datatype":"string"},"type":"statement","id":"Q512653$832B1102-580E-4C35-92B2-E4D8A18D8393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e5bbd5bf2ad6684a967ea2236cdd3fda8dfd8d1","datavalue":{"value":"Hamiltonian path","type":"string"},"datatype":"string"},"type":"statement","id":"Q512653$57CF1ADD-E587-427D-971C-71A61A293795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q512653$2895A245-87E8-4530-9797-369A97ED00D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7043ae6c9be8694f3959ce43bd348b855ba501c4","datavalue":{"value":"path partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q512653$1C6B0411-83A7-40DD-801F-9E6CB19C9C73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f49f068bfee7734b7145159f227d75f8eab452c","datavalue":{"value":"disjoint path cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q512653$865039EF-8626-4C70-A859-A233429F56D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88a5ec03ba5801b2f0f9dfca8195ccd2f7de1b87","datavalue":{"value":"prescribed endvertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q512653$1D38C919-9ECF-480C-9352-B15442C206E1","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":"Q512653$FBDE335C-A011-42D5-9D92-C9482C453066","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"21ce3b127189a3b04de2ff828daae66521df37b5","datavalue":{"value":"W2316555193","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512653$460F63D5-05B1-488E-B78D-4C7C939740C2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"38077afb4d83c5f553179729f6deb0b2a7d7a8d9","datavalue":{"value":{"entity-type":"item","numeric-id":2370445,"id":"Q2370445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$B5B471D8-18F5-42C1-BE0B-6491602ACBB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78282243e18aebf1a59d5b20c4abce65a92c037c","datavalue":{"value":{"entity-type":"item","numeric-id":2354600,"id":"Q2354600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$F48C1A3E-8767-4583-95E4-F8B1D71C5895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a7187e5c8e6052d5f7a3f5e093d9e47b869411","datavalue":{"value":{"entity-type":"item","numeric-id":3581888,"id":"Q3581888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$F27C54C8-A3EA-484E-970A-17326D2830DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"691dc8a74a183165c8aaea4f88f5c8a3b8432d9c","datavalue":{"value":{"entity-type":"item","numeric-id":2446439,"id":"Q2446439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$BCF9455E-476C-48F6-B9CF-FD7D651C17CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df1d147f9b3490dfcb11ddf26a42015d1ed8f279","datavalue":{"value":{"entity-type":"item","numeric-id":5317603,"id":"Q5317603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$6A0D540B-279B-4A10-86D1-7A999EFBABF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29029a12005eccdea1a741b5afbccd8c55e7e819","datavalue":{"value":{"entity-type":"item","numeric-id":3648508,"id":"Q3648508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$4C042484-486E-43CC-95EF-4A1500EAA227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65f985bfe9814a863785234f3c6e0b160ef6dccf","datavalue":{"value":{"entity-type":"item","numeric-id":3576719,"id":"Q3576719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$C579B94E-9910-4C9E-99AD-7A0E9B579D88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33e51d3c40c499f8d3fa3d151c55e3fb2aabda2","datavalue":{"value":{"entity-type":"item","numeric-id":708231,"id":"Q708231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$4A8139F4-95EB-45C5-9B85-8C8F11B4F5E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b342389349da4779bdd7906e3beda3158c71d6a","datavalue":{"value":{"entity-type":"item","numeric-id":975503,"id":"Q975503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$5BC52F3C-24B1-4CC7-B30C-DD1421E48C39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6828a4f9625eec04f3e1b30c583c1cca5edb60ab","datavalue":{"value":{"entity-type":"item","numeric-id":3333083,"id":"Q3333083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$885E77C2-6837-42B7-BAD5-654091D09CEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e593c46796bcc4058d7163e859d68fd22a40c46","datavalue":{"value":{"entity-type":"item","numeric-id":391966,"id":"Q391966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$6E244212-102C-46D7-96A7-1E43C33D6467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55980f69e832281e17dc901971ca7693709ffc53","datavalue":{"value":{"entity-type":"item","numeric-id":4681162,"id":"Q4681162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$350F6747-B0A9-4CEC-B92D-7F0876A40142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68ea12461e06064872d37cbba3ac0ae966ee0ff8","datavalue":{"value":{"entity-type":"item","numeric-id":1388980,"id":"Q1388980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$C7D1C37C-C9AF-4FFF-92A0-9BA92C4D105A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d676e7da7d14f9f76edbc14b8dcd731caa5f6a5c","datavalue":{"value":{"entity-type":"item","numeric-id":4376203,"id":"Q4376203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q512653$B615DE24-21BB-4684-BAE7-791D7F76D26F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b64c8f014cc6147e1c7366bddff60923ceb794b7","datavalue":{"value":"10.1016/J.TCS.2017.01.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q512653$DD384719-E9D5-4E8A-AF0B-C9E1C864823C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b05795b933ff803db675fe9c39b3a94dfcd96821","datavalue":{"value":{"entity-type":"item","numeric-id":5373994,"id":"Q5373994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a2c05f312454bee98d723f3443c978988478d06","datavalue":{"value":{"amount":"+0.8422620892524719","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":"Q512653$37E929C8-59D0-4B77-AB0C-8C8805C489B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95dafe616b95983b9a6579d88794a5832f16a5a2","datavalue":{"value":{"entity-type":"item","numeric-id":1408531,"id":"Q1408531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ace78733e8c485afcc824b5c9e15302705b6dec7","datavalue":{"value":{"amount":"+0.8379419445991516","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":"Q512653$78988035-15BD-4ADF-B661-24470799017A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f660dd93352e771e0a163b51b95c77a47c0214a5","datavalue":{"value":{"entity-type":"item","numeric-id":3575463,"id":"Q3575463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"834c2e31862a3712d2336cd6429fe0e8c370f007","datavalue":{"value":{"amount":"+0.8191238641738892","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":"Q512653$B400E180-D6A4-460A-8374-E956F66EF31A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8276219dd2546936977aeb46f9d3eb0712e48713","datavalue":{"value":{"entity-type":"item","numeric-id":5173759,"id":"Q5173759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a364b2f615c147015c2afc827492d44a8fddeb5","datavalue":{"value":{"amount":"+0.8184316158294678","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":"Q512653$E42DBC33-1B10-4A79-901C-1F4EF50742CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fd3197324d5a0a73bafc3a6a106a98536cd34c7","datavalue":{"value":{"entity-type":"item","numeric-id":1827713,"id":"Q1827713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e55e20fe2e2684e76626ff99e90c84f5569456c7","datavalue":{"value":{"amount":"+0.8136599063873291","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":"Q512653$B2274223-1ECA-4B15-B853-7E86CF0F4B97","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized Gray codes with prescribed ends","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalized_Gray_codes_with_prescribed_ends"}}}}}