{"entities":{"Q686181":{"pageid":688030,"ns":120,"title":"Item:Q686181","lastrevid":63469662,"modified":"2026-04-11T13:22:51Z","type":"item","id":"Q686181","labels":{"en":{"language":"en","value":"A spanning tree of the \\(2^ m\\)-dimensional hypercube with maximum number of degree-preserving vertices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428016"}},"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":"Q686181$0C076BC1-4030-4BF2-BD73-39832DB3B401","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8330a3dc0f3832370790d0a24cba8d32d06b143e","datavalue":{"value":{"text":"A spanning tree of the \\(2^ m\\)-dimensional hypercube with maximum number of degree-preserving vertices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686181$8DD35FDB-3E8B-4C6C-9509-B9142C4248C0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"422d249754b277daa3be53641455ac1b1de683bd","datavalue":{"value":"0783.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686181$D4B40921-B0E1-4FF8-9EC1-CB0B1A4505C8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c17cb8a0ef69cd68eb8bf27ade69724aec275839","datavalue":{"value":"10.1016/0012-365X(93)90343-R","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686181$26C4B234-D4BC-4BE2-8B3A-29962412FCC9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d342140596b3fb241508c479e183e767d9849ed1","datavalue":{"value":{"entity-type":"item","numeric-id":686178,"id":"Q686178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686181$6E82358B-FFEE-4599-A671-FF922C00968A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ea6d61bd068e1bb7e831c0f6a0376806a50ad86","datavalue":{"value":{"entity-type":"item","numeric-id":1099617,"id":"Q1099617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686181$2F0853A9-B2A5-4B61-A5E7-305E57E99B91","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":"Q686181$2684385D-E0A1-4F17-9CCC-97D7AC7CD8D8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"87ddefd6c83e22cbdb85f95663ace293dcff1d10","datavalue":{"value":{"time":"+1994-03-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686181$6A97E3B9-28DD-4E81-AF04-7AAB0361AF1C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9b0ff5caa464299f8e531c51135d308873c40ba0","datavalue":{"value":"The \\(n\\)-dimensional hypercube \\(Q_ n\\) is a graph whose vertices are ordered \\(n\\)-tuples of 0's and 1's, where two vertices are adjacent iff they differ in exactly one coordinate. \\(\\deg_ G(v)\\) denotes the degree of the vertex \\(v\\) in the graph \\(G\\). A degree-preserving (DP-)vertex \\(v\\) in a tree \\(T\\) of a graph \\(G\\) is a vertex satisfying \\(\\deg_ T(v)=\\deg_ G(v)\\). It is shown that for a hypercube \\(Q_ n\\) \\((n\\geq 2)\\) the number of DP-vertices of a spanning tree is at most \\({2^ n \\over n}\\), with equality possible if and only if \\(n=2^ m\\) holds for some positive integer \\(m\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q686181$F3A0F07E-CAFA-4417-A0B5-960566FBFDDA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686181$9D9F42F0-8E3D-4DC5-B12B-FC4BFF0452B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686181$F52A758F-E5D1-48B5-97BC-2E744357207F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3767d8c23ca7a799b16cd1bd71c042b4d2796a16","datavalue":{"value":"428016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686181$C4D97DFD-CC7D-4C63-9AAD-EDE37C5289CD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6fc2c67029cb5afd12b7d6b1fbfd27b2b2b79146","datavalue":{"value":"\\(n\\)-dimensional hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q686181$C4719528-8E63-4CFF-A236-18CD0F66A319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89c98cbdb0636239d90982c5f3d7312030f4294b","datavalue":{"value":"degree-preserving vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q686181$B51C0299-DA11-4F79-8FC4-656D20D497FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q686181$1B1BD373-D4B0-4801-8C09-A6DA28F9892E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q686181$03A7F584-A5EC-42F0-89D6-118A64CAF9CD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1b54857edcab7426c17c1bfaeb67b1f001fa1741","datavalue":{"value":{"entity-type":"item","numeric-id":587985,"id":"Q587985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686181$B7E848B7-A75E-4AFE-8E72-D33368AD927D","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":"Q686181$83E72D65-85FA-4661-9B52-5977431E0057","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686181$C54B961F-02BC-4E2F-A66A-74FC0BC1C4AA","rank":"normal"},{"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":"Q686181$222926D2-8A9B-4776-A58E-8015CB9654A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f268ffdc24678cc4482761cbf87b339c73899eb","datavalue":{"value":{"entity-type":"item","numeric-id":4146667,"id":"Q4146667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686181$9DED46C2-728F-4AE0-9FB3-39659F8F5398","rank":"normal"}],"P1643":[{"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":"9a1e5a9a4ee8f5fa3c372545bbf02af78812a520","datavalue":{"value":{"amount":"+0.7766671180725098","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":"Q686181$26A164AC-3B8A-4D2D-B079-BE9FD7AA850A","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":"447ccdd26169bce5cad14ead959df030d3aea857","datavalue":{"value":{"amount":"+0.7715546488761902","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":"Q686181$0C415466-E0B4-4985-8598-B9ADF35D38D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4eab3baf5d42f660cb0ef01dff6ab9bd7fb4fcac","datavalue":{"value":{"entity-type":"item","numeric-id":1310235,"id":"Q1310235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31f66954abdb097586f60b7362412d16f9b8da1d","datavalue":{"value":{"amount":"+0.7700930237770081","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":"Q686181$45038E96-56F7-416E-8EC3-1DA3939C9500","rank":"normal"},{"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":"50e8e2680b720072842ed003be99d7c329ceb8dc","datavalue":{"value":{"amount":"+0.7690423727035522","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":"Q686181$A831E5DD-56B9-4A32-98C3-5DB0037A963B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"295b856f3e63db5c5f306e7489f6cacfacdf33d9","datavalue":{"value":{"entity-type":"item","numeric-id":1107541,"id":"Q1107541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9640c8ba3c455d9d50afcc9c25244344f1cf52aa","datavalue":{"value":{"amount":"+0.7662899494171143","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":"Q686181$8839E58A-3649-4219-BECF-0E4B1932CDDC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A spanning tree of the \\(2^ m\\)-dimensional hypercube with maximum number of degree-preserving vertices","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_spanning_tree_of_the_%5C(2%5E_m%5C)-dimensional_hypercube_with_maximum_number_of_degree-preserving_vertices"}}}}}