{"entities":{"Q1310235":{"pageid":1320985,"ns":120,"title":"Item:Q1310235","lastrevid":67133829,"modified":"2026-04-12T15:31:08Z","type":"item","id":"Q1310235","labels":{"en":{"language":"en","value":"Spanning subgraphs of a hypercube. IV: Rooted trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 475044"}},"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":"Q1310235$5879E5E0-0F14-47B1-9D6A-064DD4227E11","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3b44a440a0eb6b99a0102e54758b0fd14cf17d88","datavalue":{"value":{"text":"Spanning subgraphs of a hypercube. IV: Rooted trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1310235$C1D6C490-3EAC-4C57-A9EE-2ECA520D06A4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae16046f828f5bd3f6d7807e87dbedfe5ace1202","datavalue":{"value":"0791.05020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310235$589523C7-6713-4CF8-9FE0-3713D94E6A36","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"700289c6ac59356e734c55b62acca6159ae5e272","datavalue":{"value":"10.1016/0895-7177(93)90258-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310235$D7FCC3C9-6F19-4BDA-B5AE-E138B01D4844","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06d35deff844ad14009ec831196ab8a1bd18feeb","datavalue":{"value":{"entity-type":"item","numeric-id":293362,"id":"Q293362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310235$9846B672-D8EA-4190-B58F-061DE031256A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"739979fc192e448573d230e187e7625c59b4c105","datavalue":{"value":{"entity-type":"item","numeric-id":1102976,"id":"Q1102976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310235$CF8E6865-F541-4F6F-AC41-DB1C23A679F4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b010567da0e068295e34b824b5eafea5ffd18ef1","datavalue":{"value":{"entity-type":"item","numeric-id":166953,"id":"Q166953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310235$2B9BDED8-9963-42BD-8F9D-5ACA8C37472C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ecd7f48b759dfd821149e625b4185349d418788b","datavalue":{"value":{"time":"+1994-06-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":"Q1310235$312B7B44-AF98-449E-974C-611907D8923A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3bf9b86b2f2571c1b9cc1469ccc86779fd0c9839","datavalue":{"value":"Let \\(T\\) be a spanning tree of the hypercube \\(Q_ n\\), rooted at the origin \\(u_ 0\\). Define a function \\(g:E(T) \\to\\{-1,+1\\}\\) as follows: If \\(e=xy \\in E(T)\\) is such that \\(d_ T(x,u_ 0)<d_ T(y,u_ 0)\\), then \\(g(e)=\\sum (y_ i-x_ i)\\). Define \\(f(T,u_ 0)=\\sum_{e \\in E(T)} g(e)\\). The authors prove that \\(2n+1-2^ n \\leq f(T,u_ 0)\\leq 2^ n-1\\) and that the bounds are tight.   Given a spanning tree \\(T\\) of \\(Q_ n\\), the root \\(u_ 0\\) can be varied over the \\(2^ n\\) possible vertices. Denoting the corresponding values of \\(f(T,u_ 0)\\) by \\(f_ j(T)\\), \\(1 \\leq j \\leq 2^ n\\), the authors further prove that \\(\\sum^{2^ n}_ 1f_ j(T)=n2^ n\\).   If \\(S=\\{T_ 1,\\dots,T_ s\\}\\) is the set of spanning trees of \\(Q_ n\\) and if \\(k\\) is any positive odd integer between \\(f(T_ i)\\) and \\(f(T_ j)\\), for \\(1 \\leq i\\), \\(j \\leq s\\), then the authors prove that there is a spanning tree \\(T_ h\\) in the set such that \\(f(T_ h,u_ 0)=k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310235$65D19F64-34F8-47A4-A26D-2282B47DEEF5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310235$DAAB3F3F-7016-4C76-BF08-41FB8D3F9FEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310235$9ECEB257-0B3B-47F1-BA95-D3072416B879","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4131c7a3b88686e67a8eda3dc1b209491dfd6e7d","datavalue":{"value":"475044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310235$092F6AE7-34F8-4AC4-9E71-2AC4872497ED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62f0a460613792c7b1d98ca7c82b87b4b903b963","datavalue":{"value":"rooted tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310235$0302F1A4-F10F-4045-9ACB-5B6846409872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310235$D4A5F8A3-9492-4F52-A300-FFB3626EA60E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310235$4EE57CDA-818F-4C5C-B67B-3DA3AAABA05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b77b431fc86a92792dc6a21fc772bba2088fb678","datavalue":{"value":"bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310235$3829B8DC-3898-4046-AF2E-90FFD2652BEC","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":"Q1310235$06D3E81F-0D3A-4B01-A257-7720DC3B74AE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"16b286c01c639847423d2b6cfad3ca0d88e786da","datavalue":{"value":{"entity-type":"item","numeric-id":1102977,"id":"Q1102977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310235$BFB57FB2-EF8B-4CB1-AAD4-B637A5E3A896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9087c9bf809b6e9ce1b0c7763fa79174bc3c0a28","datavalue":{"value":{"entity-type":"item","numeric-id":3717071,"id":"Q3717071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310235$808EA802-8A46-467A-B62E-200667CE8858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0964805f7791eeba7d64f74eebcdb82812fdc606","datavalue":{"value":{"entity-type":"item","numeric-id":3329492,"id":"Q3329492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310235$A9EDC418-6144-403F-A6C1-15996315AF50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfd72552458bdb779251e428b92b8185d8df41b4","datavalue":{"value":{"entity-type":"item","numeric-id":3309850,"id":"Q3309850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310235$A3500264-DED3-4658-8519-BCF130B5F8F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a32206070c87ae3ad2d59544e793183aec569b59","datavalue":{"value":{"entity-type":"item","numeric-id":3939828,"id":"Q3939828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310235$F248BB89-C45E-4C12-B1EE-81243E499B3D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8eaff6cfa1bab7295fcca8abdfea02fdf372af7a","datavalue":{"value":"https://doi.org/10.1016/0895-7177(93)90258-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q1310235$4014C089-ED5E-4862-BEBB-6B91BFAB66A1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f91cd9b3ec233383aed3bd82a9a027ade0e436e4","datavalue":{"value":"W2059164288","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310235$EDAD27F6-06DF-49FB-BA7F-758326E08A57","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c844d1114fb17e11f62ad0c8e8813a9517c384cb","datavalue":{"value":{"entity-type":"item","numeric-id":3333083,"id":"Q3333083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f81c5422162e7872e44ec949a192e4815083dfdb","datavalue":{"value":{"amount":"+0.814683198928833","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":"Q1310235$06FAA3F9-0992-4B27-84D5-8C7DDB1ED350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a9ea660c1caeae73cfe5eeea82edb4d0a403e9d","datavalue":{"value":{"entity-type":"item","numeric-id":4294594,"id":"Q4294594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15cfc4df5a6a85111ea88eefad10fcf183795e74","datavalue":{"value":{"amount":"+0.8066207766532898","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":"Q1310235$D9693993-CA82-4B0B-99A9-4E00567D384A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d4062a21a2723b43284631a9873d6c90bd55b59","datavalue":{"value":{"entity-type":"item","numeric-id":1388974,"id":"Q1388974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1743052944847baab95cf45b8d5493fb29c14047","datavalue":{"value":{"amount":"+0.802443265914917","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":"Q1310235$1A8D33A1-38E5-4341-B3AA-952354461BC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19211932ddcebdd5ce918e4fc2fa9dc652ac15a7","datavalue":{"value":{"entity-type":"item","numeric-id":5950587,"id":"Q5950587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfb8ea718e63a1579a13486da5f7609cf88549b5","datavalue":{"value":{"amount":"+0.7939673662185669","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":"Q1310235$295C9A90-04CD-45EA-9CB7-2D52EBDEB368","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":"a9e1b9a7d2208c3775867394d4db9dd587118fb4","datavalue":{"value":{"amount":"+0.7829984426498413","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":"Q1310235$7CC176CD-A93C-4406-8C1E-9AF9474505EC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Spanning subgraphs of a hypercube. IV: Rooted trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Spanning_subgraphs_of_a_hypercube._IV:_Rooted_trees"}}}}}