{"entities":{"Q5936018":{"pageid":8112820,"ns":120,"title":"Item:Q5936018","lastrevid":41928445,"modified":"2025-05-16T12:37:29Z","type":"item","id":"Q5936018","labels":{"en":{"language":"en","value":"Optimal embeddings of generalized ladders into hypercubes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1612878"}},"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":"Q5936018$DCCB7ABB-00D9-4599-9199-CAE32D257AF3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1d1eaa1d11c6a6b64ca835db6b9ca987ecb89748","datavalue":{"value":{"text":"Optimal embeddings of generalized ladders into hypercubes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5936018$EB035893-089F-4517-A1CC-A7E3702B36AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a25227f29a2476905ff659593547fccda9a8fb61","datavalue":{"value":"0986.05034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936018$E4F47FE1-91E5-4E23-9582-50DD5EDABF1E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b919c980e450ec5c15d0a7afd173194d9a8399b6","datavalue":{"value":"10.1016/S0012-365X(00)00227-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936018$16EE0099-3224-47D6-830E-B9A4EF48DBBE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"baf5c1d5088b50ef7f3c2bbfee959c7fb7775ca7","datavalue":{"value":{"entity-type":"item","numeric-id":2370444,"id":"Q2370444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936018$A3322BB9-3681-49B5-84E9-3A23F2A82E43","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":"Q5936018$BEF67717-D82D-4D2E-A833-2739FF198205","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":"Q5936018$AE0C844F-C4E9-48A9-8E21-21C799DE0093","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca81d64c0b12a62d219fb28ceff571fa6ba75361","datavalue":{"value":{"time":"+2002-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":"Q5936018$29D866C4-A085-4FAC-9A36-C05099784968","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":"Q5936018$9DDD39E3-43FC-4A69-B742-7FDE7D8033BF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936018$00F0BCF4-8CA5-4A2D-97A2-81C87B143D01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936018$BDFFB2AB-4E67-4159-A81D-C526B83F3DB0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4562cccf81fddd08867cfdec62c0140b8e67a434","datavalue":{"value":"1612878","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936018$A732ED0B-32F3-43B0-93F0-CEDE845B300B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86d9b4ad5a06064fd9c9bcbc50f8026b1c776dc","datavalue":{"value":"embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936018$0124EAFC-4471-4680-BB19-935C37AF081C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c85e5c4a2efae4ba772474132eb229a89b4c3b2","datavalue":{"value":"generalized ladders","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936018$E6561FCC-7C8A-40C2-AEA4-D1130E0B25E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936018$6DDC9A74-D7A7-4778-A358-62BCFE340F7D","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":"Q5936018$5049EBAF-1432-45CC-92A5-B12CFF197969","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"973b8e02bd0dd62653f9627814b3228cfc3339d3","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00227-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q5936018$70E16713-3240-42A4-A86C-42A5C0189C1D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1072b81b8d689d116743c8cb50d2651fb17df2bf","datavalue":{"value":"W2042456687","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936018$9DCD94B2-1891-4B04-94C8-A5B156D128A8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3547d3a5e65c2d4212f6d39356de724dc84c1e96","datavalue":{"value":{"entity-type":"item","numeric-id":5957299,"id":"Q5957299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70c20b70b6f0e41aaf22e187b632f70e5951a415","datavalue":{"value":{"amount":"+0.80216956","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$A5C922E7-0024-4933-8F21-98CCBFA60278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c36094563e73beafe51c1de53ceedb9da11b9d96","datavalue":{"value":{"entity-type":"item","numeric-id":4638647,"id":"Q4638647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee53221a4c477e28c86d2a2f4cbce9cf7a64341a","datavalue":{"value":{"amount":"+0.7838306","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$6305C5E3-3D1E-4EB1-8579-C1EF3A7C264E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd597a2e871d0d083312482820a96f3d354300f6","datavalue":{"value":{"entity-type":"item","numeric-id":1006750,"id":"Q1006750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55db6566974c654fe12dc2f89ab7172e354b2135","datavalue":{"value":{"amount":"+0.76163244","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$DF086138-3737-4B34-8CC2-9AAFE19063AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1b0b2b82194502ae8af905ded3ad4895d3532af","datavalue":{"value":{"entity-type":"item","numeric-id":5249653,"id":"Q5249653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd588c7902093dd66b5fe2e4e87e99e0ae8b9b7f","datavalue":{"value":{"amount":"+0.74685013","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$62D0F05B-76EA-4C9D-A07D-E4602BCB8236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6be564dbdf08d3d32ad8717289b02da211c34ef","datavalue":{"value":{"entity-type":"item","numeric-id":3717071,"id":"Q3717071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73ee992b856eeb8620e53f634871d32736e12ac7","datavalue":{"value":{"amount":"+0.7420932","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$D53870BB-EB67-463A-84B4-55CC4C286C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f401744afda72f2a78b0551d7e8a1b6aadeba298","datavalue":{"value":{"entity-type":"item","numeric-id":1178228,"id":"Q1178228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e826643e2d2eeb91804a1ffa3c17910348fefa6","datavalue":{"value":{"amount":"+0.7253603","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$5D868354-6E8E-4949-B119-5BB8D03D8736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf5cd22d1b6214c40792cf09b9f47f3fbfafe9b5","datavalue":{"value":{"entity-type":"item","numeric-id":3633839,"id":"Q3633839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c38e9202327a8976122b90071b5f6039ca51924b","datavalue":{"value":{"amount":"+0.7185935","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$60A4AC63-5748-487B-B4F6-74D2AC448EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed28940df7bd231e5cb01c3f94e700868493b2da","datavalue":{"value":{"entity-type":"item","numeric-id":1066918,"id":"Q1066918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94b0bc3e64714df1bd035973fadb0f9f107507ba","datavalue":{"value":{"amount":"+0.7150882","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$556627C0-502C-4380-B0BF-077E13376EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b67a746dcbad5b0b8f9b0a0025153c22c2e1254","datavalue":{"value":{"entity-type":"item","numeric-id":1392524,"id":"Q1392524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a1a52961daf9ed7f675a9ed85186db2dce71a36","datavalue":{"value":{"amount":"+0.71461946","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$3E7EABD1-DA1C-42CA-AA7F-46CBD7D6360F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4c9d463cfc1758479c8a996361cc07eebc4accb","datavalue":{"value":{"entity-type":"item","numeric-id":396672,"id":"Q396672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f6892ac0ab8a9fcdf20c47e953df0043aa7293b","datavalue":{"value":{"amount":"+0.7127054","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5936018$51965B97-E8C3-4F18-A204-C92FED6D769D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab530c21bf5e42b8e4a470fecbdefce4837ef460","datavalue":{"value":"A hypercube of dimension \\(n\\) is a graph whose vertex set consists of all binary vectors of length \\(n\\), two vertices being adjacent iff the corresponding vectors differ in exactly one coordinate. A graph \\(G\\) has an optimal embedding into a hypercube if \\(G\\) is isomorphic to a subgraph of the hypercube of dimension \\(\\lceil\\log_2|V(G)|\\rceil\\). Any hypercube is balanced, i.e. a bipartite graph with equal-sized classes of bipartition. Motivated by a conjecture of \\textit{I. Havel} [\u010cas. P\u011bst. Mat. 109, 135-152 (1984; Zbl 0544.05057)] saying that every balanced tree of maximum degree three has an optimal embedding into a hypercube, \\textit{S. Bezrukov} et al. [Discrete Appl. Math. 83, No. 1-3, 21-29 (1998; Zbl 0906.05019)] showed that an optimal embedding exists for another class of balanced graphs, called ladders with even rungs. This paper generalizes their result. NEWLINENEWLINENEWLINEThe authors introduce a generalized ladder as a graph \\(G\\) consisting of two disjoint paths \\(P_0=(x_0,x_1,\\dots,x_n)\\), \\(P_1=(y_0,y_1,\\dots,y_m)\\) and \\(p\\) pairwise disjoint paths \\(R_i=(z_{i,0},z_{i,1},\\dots,z_{i,l_i})\\) for \\(i\\in\\{0,1,\\dots,p-1\\}\\) such that each \\(R_i\\) has exactly one vertex \\(z_{i,0}=x_{j_i}\\) (\\(z_{i,l_i}=y_{k_i}\\)) in common with \\(P_0\\) (\\(P_1\\)) for some \\(j_i\\in\\{0,1,\\dots,n\\}\\) (\\(k_i\\in\\{0,1,\\dots,m\\}\\)) and moreover, \\(j_i<j_{i'}\\) (\\(k_i<k_{i'}\\)) for all \\(i<i'\\). \\(G\\) has even (odd) rungs whenever all \\(l_i\\)'s are odd (even). The main results of the paper are optimal embeddings into a hypercube for two classes of generalized ladders: balanced generalized ladders with even rungs, and so-called pretty generalized ladders, which form a proper subclass of balanced generalized ladders with odd rungs. The proofs are based on sophisticated inductive constructions which generalize methods of Bezrukov et al.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936018$E91CFDA2-52B8-42F6-84C5-A6E3B783AC6E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5936018","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5936018"}}}}}