{"entities":{"Q1045206":{"pageid":1047054,"ns":120,"title":"Item:Q1045206","lastrevid":66119619,"modified":"2026-04-12T07:40:41Z","type":"item","id":"Q1045206","labels":{"en":{"language":"en","value":"Spanning tree congestion of the hypercube"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5648226"}},"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":"Q1045206$50F5ED11-6CF4-4163-B4BC-F3FEB0459417","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc4128d15ccf7397f062a9641dfd08baa3119f7e","datavalue":{"value":{"text":"Spanning tree congestion of the hypercube","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1045206$2151A2F2-9101-4874-8ED9-5DDD9121D726","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"65dd6032cfd1a59dedeae56af722516e3976018c","datavalue":{"value":"1179.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045206$C1494D3C-2337-4E58-A22F-D9788EB21865","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"49d0bae6dd7abd940b414cce3dced804adf295ab","datavalue":{"value":{"entity-type":"item","numeric-id":298940,"id":"Q298940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$CCBB30BC-AFF0-46C6-947E-684CE8CF4AE7","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":"Q1045206$1FD85079-9014-42BD-883E-288A6D4F4BA7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9d265d400060d2e7fb9c5c45adc5a5c7f5f7bbd7","datavalue":{"value":{"time":"+2009-12-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1045206$94D7350E-ED5B-4DCE-8F40-84D28D060C9F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2b09b70107a499c593cfc54fae0e26b22f813b3e","datavalue":{"value":"The main purpose of the paper is to estimate the spanning tree congestion (introduced by the reviewer in [\\textit{M. I. Ostrovskii}, ``Minimal congestion trees'', Discrete Math. 285, No. 1--3, 219--226 (2004; Zbl 1051.05032)]) for hypercubes \\(Q_d\\) which are defined as graphs whose vertex sets are sequences of \\(0\\) and \\(1\\) of length \\(d\\) and two vertices are adjacent if and only if the corresponding sequences differ at exactly one position.  The spanning tree congestion of a graph \\(G\\) can be defined as \\(s(G):=\\min_T\\max_{e\\in E(T)}\\# e_G(A_e,B_e)\\), where the minimum is over all spanning trees, the maximum is over all edges of \\(T\\), and \\(\\# e_G(A_e,B_e)\\) is the number of edges in \\(G\\) between the vertex sets of the components of \\(T\\) obtained after the removal of an edge \\(e\\).  The most important and interesting result of the paper is an upper bound for \\(s(Q_d)\\) of the form \\(O(2^d \\log_2 d/d)\\). This bound disproves the conjecture of \\textit{Stephen W. Hruska} [``On tree congestion of graphs'', Discrete Math. 308, No. 10, 1801--1809 (2008; Zbl 1151.05014)] on the value of the spanning tree congestion of hypercubes.  The author also found a lower bound of the spanning tree congestion for hypercubes which is close to his upper bound. The lower bound uses the isoperimetric technique suggested by the reviewer [op. cit] and the isoperimetric inequality of \\textit{F. R. K. Chung}, \\textit{Z. F\u00fcredi}, \\textit{R. L. Graham} and \\textit{P. Seymour} [``On induced subgraphs of the cube'', J. Comb. Theory, Ser. A 49, No. 1, 180--187 (1988; Zbl 0653.05037)]. Independently a similar lower bound was obtained by \\textit{K. Kozawa}, \\textit{Y Otachi} and \\textit{K. Yamazaki} [``On spanning tree congestion of graphs'', Discrete Math. 309, No. 13, 4215--4224 (2009; Zbl 1232.05116)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1045206$F9DAF83B-0B97-4653-8B35-E91777A482E8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045206$3BEAB430-27F8-4291-B5C1-DD08401BABD9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2778c6b64d4d7279b8281549c79218550a5630ef","datavalue":{"value":"5648226","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045206$E5A713F1-3D34-43C9-A255-FE952453C72D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1da2a62ba1d4ac8921f27585274cca2040821355","datavalue":{"value":"spanning tree congestion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1045206$9055B6A9-63C1-4797-9E9D-C227C7C703DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6193e72d9a4afc7584aaf6b5f67e8878aff820f","datavalue":{"value":"minimum congestion spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1045206$E7A9DE26-84D4-45F6-AB36-359CA2181ADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1045206$98E23004-61BC-4A68-B799-655005B120A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b02f8a32f4298c90cc596256391759641cbbf04a","datavalue":{"value":"edge-boundary","type":"string"},"datatype":"string"},"type":"statement","id":"Q1045206$22FB62E1-F4F7-46D5-9127-9B87890C63B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"812c062dfe6a4b116e1217d30c74249a0c6ddd71","datavalue":{"value":"isoperimetric inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q1045206$8DCC9EBD-EC5F-40D9-8B4E-2F02C2291A4A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"14ba19fd9284d2cf0d8decec72dc0f5317181977","datavalue":{"value":{"entity-type":"item","numeric-id":394136,"id":"Q394136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$D1685A9D-6F07-465F-9651-3B444D96C23E","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":"Q1045206$418957AA-71DD-4615-9181-C3DB0C9BBD2A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6c226f5df4a3124131a8e60d93b505e3fe082ddc","datavalue":{"value":"https://doi.org/10.1016/j.disc.2009.07.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q1045206$B4FBFA8F-2129-433B-90B7-C6E6BE7E8958","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a1c56139f143d49d9aa4b39af8943d7946f96a1f","datavalue":{"value":"W2764962283","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045206$3249EB0F-A014-4815-90C5-AD800AC12468","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"75f8b250eadfcdf0e383260f1cdf4e043adb9d50","datavalue":{"value":{"entity-type":"item","numeric-id":5539520,"id":"Q5539520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$2A5314D6-D671-4239-91D0-83A177FD126C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a25dd75a19e15ef5ea88e541e25df7fe0541280","datavalue":{"value":{"entity-type":"item","numeric-id":3560779,"id":"Q3560779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$2C68B9F7-889D-4295-B40E-539143340CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a369e00d222394499fbeac6ef2d4a8f0d1db95e1","datavalue":{"value":{"entity-type":"item","numeric-id":1107541,"id":"Q1107541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$71E48BE3-EACF-4A4A-B82D-78BFB71E316F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dce4985f6cbf3d8009e6b46a8c38dfdc42d02e4","datavalue":{"value":{"entity-type":"item","numeric-id":5627967,"id":"Q5627967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$D30CA066-7EE8-4808-9BED-AB10231FA103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5170fae3f9614405dec612782eecdb7dffd9b1b8","datavalue":{"value":{"entity-type":"item","numeric-id":1240261,"id":"Q1240261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$52B3210C-50F0-497E-9916-D577505629A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8364a371a73fd9eab9cf13588ee1d4ea3fa4e2d2","datavalue":{"value":{"entity-type":"item","numeric-id":952638,"id":"Q952638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$D2B29D24-7C62-4FCA-8E29-AA118B96A419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bd00e1112a4dbd12f8cc2c8c9418adfb672c595","datavalue":{"value":{"entity-type":"item","numeric-id":3976405,"id":"Q3976405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$599E56AC-7244-4413-AABB-A29E56A398AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75e0aa33df61f842fad597cf4b3976cf9a1ad1ff","datavalue":{"value":{"entity-type":"item","numeric-id":4404912,"id":"Q4404912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$E7F177E6-ACE9-4DE2-B87F-13D015CBC6C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98bf849e57b91309a964f14b152686c4440498d3","datavalue":{"value":{"entity-type":"item","numeric-id":1877665,"id":"Q1877665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1045206$698ABAE5-7FF3-488D-A3E5-12EA4B87F5F9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c828d2a48c7095fe5bc9bfee7c32ce099d873560","datavalue":{"value":"10.1016/J.DISC.2009.07.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1045206$212A696F-6CB2-4F71-80D9-A59AC1312167","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"316c15198a66997b49a595ffbb8ba329dbca48d3","datavalue":{"value":{"entity-type":"item","numeric-id":1043936,"id":"Q1043936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4aeac087e430740a8818881961c2bde6fae643e2","datavalue":{"value":{"amount":"+0.8303684592247009","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":"Q1045206$C1721914-D2E3-4845-88C8-B5EC17025F41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c99e2ffcecd884a6f3e2ed7feb6af1671600ec5","datavalue":{"value":{"entity-type":"item","numeric-id":1877665,"id":"Q1877665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5eaee1e8140b4d62489512e1cd07c370c2a6a4bb","datavalue":{"value":{"amount":"+0.8040531873703003","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":"Q1045206$3468B86F-B8AC-40EC-8284-B9449CE8BEA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbf5e6c157ca9c39c59044b3dc35f20c626e7bac","datavalue":{"value":{"entity-type":"item","numeric-id":1349091,"id":"Q1349091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f35fc96a97630270999c990edb83c4be591b30af","datavalue":{"value":{"amount":"+0.7904154062271118","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":"Q1045206$A8B57410-5E1C-4D29-9557-ED9AEE00D481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee1e0a364cab24139481603e9f9aa68ec815e2d2","datavalue":{"value":{"entity-type":"item","numeric-id":2906358,"id":"Q2906358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94ea20d369d6b56e30f18e0ed9ae93d163306785","datavalue":{"value":{"amount":"+0.7896027565002441","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":"Q1045206$C96A04AF-6C75-4CEE-A8A0-5D6DF6BECBAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5e95f73ce4f131b608c5d3dc45509ee8682912b","datavalue":{"value":{"entity-type":"item","numeric-id":4540091,"id":"Q4540091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"296b983e554f834476e8e1bb1cf5331518a069bc","datavalue":{"value":{"amount":"+0.7865943908691406","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":"Q1045206$CA180D25-5609-48E4-8E74-1C74C2E94DD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Spanning tree congestion of the hypercube","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Spanning_tree_congestion_of_the_hypercube"}}}}}