{"entities":{"Q1868842":{"pageid":1879584,"ns":120,"title":"Item:Q1868842","lastrevid":73593444,"modified":"2026-04-14T16:35:00Z","type":"item","id":"Q1868842","labels":{"en":{"language":"en","value":"On paths and cycles dominating hypercubes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1901894"}},"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":"Q1868842$1F3AB8A3-DE48-468A-942A-825945FC4C2E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63774f32a333026c97b83097ace0089c3d57d138","datavalue":{"value":{"text":"On paths and cycles dominating hypercubes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1868842$A999CBBD-3DE4-473E-8C2D-E87B7003ACA6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8f80cc9fe5385e85526eed76409d0ad70ae10102","datavalue":{"value":"1012.05122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868842$C49AD584-8E2A-4113-880C-55641B29371C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d9a7236801ad65f2f1fa482ea461085fa16a51f","datavalue":{"value":"10.1016/S0012-365X(02)00524-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868842$0AE7686F-3EBE-4FDB-A14F-514E7C5BEC42","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":"Q1868842$3C1FA972-878F-4293-AE88-EA6E248DBBD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d845924fbb15f51c1675b5dbbaba29caeae223fd","datavalue":{"value":{"entity-type":"item","numeric-id":190527,"id":"Q190527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1868842$B591198E-B0F3-48C8-8095-0F76BBA94C3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d08a6f9c3b013f966058b4be820a36b59b06917d","datavalue":{"value":{"entity-type":"item","numeric-id":1134529,"id":"Q1134529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1868842$42DF2057-3930-4934-9C90-BDCA7D75CEC3","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":"Q1868842$5A2A28FD-02A5-4184-95FB-013B765BD359","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3b05751a28df8b7d171e02c18dec5082d33efa41","datavalue":{"value":{"time":"+2003-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1868842$4006EF9D-750E-41EE-8EF4-CDED0AC14500","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b7a8f8e86d7d03af058765c9207c42e5f1ad79b1","datavalue":{"value":"Let \\(\\text{c}_n\\), \\(\\text{p}_n\\) and \\(\\text{cyc}_n\\) denote the minimum number of vertices in a dominating set, a dominating path and a dominating cylce of the \\(n\\)-dimensional hypercube, respectively. The authors prove that \\(\\text{cyc}_n \\leq 2^{m-p}(2^k+2)\\) for \\(p\\geq 2\\), \\(m=2^p-1\\), \\(1\\leq k\\leq 2^p\\) and \\(n=m+k\\), \\(\\text{c}_n\\geq 2\\lceil\\frac{2^{n-1}-2}{n-2}\\rceil\\) for \\(n\\geq 3\\) and \\(\\text{cyc}_n \\geq 2\\lceil\\frac{2^{n-1}}{n-2}\\rceil\\) for \\(n\\geq 4\\). Furthermore, they prove so-called interpolation results for \\(\\text{p}_n\\) and \\(\\text{cyc}_n\\): For every \\(n\\geq 2\\) and every integer (even integer) \\(i\\) with \\(\\text{p}_n\\leq i\\leq 2^n\\) (\\(\\text{cyc}_n\\leq i\\leq 2^n\\)) there is a dominating path (cycle) containing \\(i\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868842$E0CE5926-164A-4627-9673-F3DF645BF776","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c21cb54e7c2c469712a9307e52fa5ab7414ba5da","datavalue":{"value":{"entity-type":"item","numeric-id":186196,"id":"Q186196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1868842$1EC77330-7519-4B5A-81DC-83BF7B8977FB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868842$83EC066A-5490-438A-9171-4D71D1ECD042","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cab8b09ecd27642aa673c231afe499ba3cf71145","datavalue":{"value":"1901894","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868842$02973174-9A9B-4D17-8CC4-F41BD6503B41","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f607710e1bcd8426818fbf0effed996082aed3f","datavalue":{"value":"domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868842$BBFB8991-B042-42CE-997E-7EF349ED4128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868842$39888002-B4DB-4E0C-BC8E-4AC4B382C2F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca64234e91f064fb156f7b79929000d7d8daf9d5","datavalue":{"value":"dominating path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868842$E285A217-1979-411C-A24E-1E14F4389C9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c975ab5bc8d729ed0ef9c8d859287541463d71c1","datavalue":{"value":"dominating cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868842$968395BE-51ED-4BB6-A61F-F698CABEC411","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":"Q1868842$734FC10F-B237-48FB-AC0A-8184E304AFD7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e186491f25d21e1327790b532c72b0e5a1e257e3","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(02)00524-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1868842$59962662-F63A-464A-A65E-1AE0F458769D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c7412a6134bf33447982e65e345f3ec69f2ccaf0","datavalue":{"value":"W1975699957","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868842$63B60FA6-3C06-4B35-9CBA-D906FD4C11B1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef5b16f74c0cda3b291ceb128be4e86c7f2544fa","datavalue":{"value":{"entity-type":"item","numeric-id":5939208,"id":"Q5939208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"386fae2def84bf467c53442f57f76f99c078940b","datavalue":{"value":{"amount":"+0.93262637","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$385FA300-EFC9-4E9F-8AFC-52761D1B50A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c6587b890b0a653b4665001a55eb165d0fc2e6c","datavalue":{"value":{"entity-type":"item","numeric-id":987833,"id":"Q987833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49f69225a9f83b0a0adece30433e73d7aa097bd8","datavalue":{"value":{"amount":"+0.93119735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$D30CD37B-2B2F-4096-982C-23A836C0E364","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e977460af578eb26a1e0fcb934a69591c1d4049a","datavalue":{"value":{"entity-type":"item","numeric-id":5257457,"id":"Q5257457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50751227a6ed2bb07d6b51f1ad73cbc1d57ada9d","datavalue":{"value":{"amount":"+0.92409486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$05C6035E-8556-41EA-92F4-2F9AB22FA2FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cc9e0a1de4386c6d1f189eeecf0d01caa923e94","datavalue":{"value":{"entity-type":"item","numeric-id":1283074,"id":"Q1283074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55a3f7dfe91f84719facf51f0cd27ace3d48b6e4","datavalue":{"value":{"amount":"+0.92280346","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$737F7FE8-4056-4770-9175-BFD0001CAA42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"596074cf5d280485c9cb0cdc4c89c86ea7df062a","datavalue":{"value":{"entity-type":"item","numeric-id":845903,"id":"Q845903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b4985eaeb2a5ef8b054f84451755414a416df02","datavalue":{"value":{"amount":"+0.9181943","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$03C39F39-B7A9-4AC1-BD9C-85FF445824EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42682b3d14949b2da7b6b7ae818f11cfbaa06bb2","datavalue":{"value":{"entity-type":"item","numeric-id":990940,"id":"Q990940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36692743ffbe706f741020ea24a5ccfac3d32bff","datavalue":{"value":{"amount":"+0.916598","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$F6516A74-8CFA-4871-9FAC-5676172DC86C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae5d33df4def99f993cd3b2d385dd777a45b38c4","datavalue":{"value":{"entity-type":"item","numeric-id":4004439,"id":"Q4004439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b07611770d75cdfe4f989eff2d111558b359039","datavalue":{"value":{"amount":"+0.91627395","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$CC842589-C008-4A87-8C24-A8E660110739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"111cc34ad7aa3feaeef722e557f5607e48a97f69","datavalue":{"value":{"entity-type":"item","numeric-id":2345537,"id":"Q2345537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4701abfb63fb993155c34c0e6b3f793a19c0867a","datavalue":{"value":{"amount":"+0.9134437","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$FD98FA39-1E22-4D14-A6CC-4A0BB296E49B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b73032a90938a0bbfe76aff63ef4e2a68bcb1ebf","datavalue":{"value":{"entity-type":"item","numeric-id":3576719,"id":"Q3576719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3363f932525e6e1a593e732040fd41b6a97eedf","datavalue":{"value":{"amount":"+0.90587723","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$0FD99086-7088-4DBC-973E-F51B1D6B7A98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e238b8af38f4498a346b3a264cb2d38b6166fe5d","datavalue":{"value":{"entity-type":"item","numeric-id":688627,"id":"Q688627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abe638dad4b4757ca85dcbe19b5ac21fce1f8a9c","datavalue":{"value":{"amount":"+0.9058589","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1868842$1DA44117-1ADE-4D18-85F2-807D9CFA0898","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On paths and cycles dominating hypercubes","badges":[]}}}}}