{"entities":{"Q1972147":{"pageid":1982889,"ns":120,"title":"Item:Q1972147","lastrevid":72109941,"modified":"2026-04-14T02:42:59Z","type":"item","id":"Q1972147","labels":{"en":{"language":"en","value":"Higher edge-connectivities and tree decompositions in regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1423746"}},"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":"Q1972147$F4FAF108-00F6-49BA-974A-17276F400FD4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ab3d4d5342537c1e44a075c8526e93ee62fb326","datavalue":{"value":{"text":"Higher edge-connectivities and tree decompositions in regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1972147$D01AD636-0C9C-4C24-AFCD-202843C417A2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c1e5559fc74760c53996e9eee2e53b23c87cef0f","datavalue":{"value":"0941.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972147$9193F751-B381-4E8B-8E4D-66C85CBEF27C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"128bb42603ff204f3d0df179eaab7ac52042d176","datavalue":{"value":"10.1016/S0012-365X(99)00314-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972147$3AE95430-55BC-470D-A8DD-6CE7316AD257","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972147$FE27A32D-AAF8-439D-9A67-FC2308D8C5E2","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":"Q1972147$43BF6827-5C4D-41FA-94A2-BD989DCFE3C8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fd4b049ed45c807df2d896dae78bc4c4cca7a746","datavalue":{"value":{"time":"+2000-07-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1972147$B7E8DFDC-11D0-48FE-AFF0-95783E4EB094","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5e0d04c827b39225407f76da89259b4f08718cb4","datavalue":{"value":"A tree decomposition of a graph \\(G\\) is a family of subtrees whose edge sets partition the edge set of \\(G\\). The arboricity, \\(a(G)\\), is a trivial lower bound of \\(\\tau(G)\\), the minimum number of trees in a tree decomposition. In the paper it is proved that \\(a(G)=\\tau(G)\\) for all regular graphs of order \\(n\\) and degree \\(d\\geq \\lfloor n/2\\rfloor\\). This bound is best possible. The proof uses higher edge-connectivities, which also provide sufficient conditions for \\(a(G)=\\tau(G)\\) when \\(d>\\sqrt n\\) and \\(G\\) is a hamiltonian graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972147$7048A367-3FE5-4A76-81C2-7F0CB24924BC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8146f5feb228c23e2fa6738cca425f9e847fc191","datavalue":{"value":{"entity-type":"item","numeric-id":335340,"id":"Q335340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972147$360C867F-4ADE-46F3-A6AD-0DEE44A6BE29","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972147$762A44B5-793E-47E2-8029-A19673F38FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972147$FEF1C54A-4E18-4BB4-AB12-3FE5CF0972CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972147$89DD63F6-9172-4405-8F9A-2C0D6005EBF7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"370ad87415d461c1ee6c203d151928726f514407","datavalue":{"value":"1423746","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972147$C1EBF7E8-DB71-43F4-81E1-8C484314E2C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1e625afea5b1a633df9fe58ad43c2d03e075ec","datavalue":{"value":"tree decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972147$77707709-6FAC-473B-98D5-ECC00F515C95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33d42ddf4e1ea41f5d8846555ec9a668fbb0211f","datavalue":{"value":"arboricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972147$0DF37B67-27A9-4678-8036-1394A6A0206F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9217cf5fdf9311e03b0d651a5eac92fd9c7100c2","datavalue":{"value":"regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972147$1BB56AAD-98BD-4580-B1A4-973A7D9FB92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0f71c045d177c93460d81ad018a2f4ca3ac5286","datavalue":{"value":"\\(r\\)-edge-connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972147$48EC7BE6-C6CC-4348-B40F-E55647F3AB8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a82e5042bc8e8b4dcb6c1dff69ae5ae8fb8e33e","datavalue":{"value":"hamiltonian graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972147$7AB7BC78-8D48-46B9-B134-1BF8578BB13D","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":"Q1972147$7C7D127C-0F53-4247-AFF7-792C045C3F93","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9df2e5c2a6a6d1ab9812fcf2f69cac9ce939ba2b","datavalue":{"value":"Q127442889","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972147$C52882A4-4EDA-450D-99EB-79935B0A2ED0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37ff284b09e8acdd59b92e8b8721b8ee7bd75700","datavalue":{"value":{"entity-type":"item","numeric-id":1356782,"id":"Q1356782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"500670ad6018893bc190ea4661d4baa51573965d","datavalue":{"value":{"amount":"+0.8843541145324707","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":"Q1972147$51B1EA31-921D-4315-BF2D-F5D9BC1F9669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85df7c82a7c1fe5fc6e983a1a5ce53f826825cbb","datavalue":{"value":{"entity-type":"item","numeric-id":3745866,"id":"Q3745866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9df27437e6abca612a91522d7824d5d8fb78d11c","datavalue":{"value":{"amount":"+0.8828344345092773","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":"Q1972147$B99AD0AE-C938-4A6D-918D-8D170F95F320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33021ae9189c6bc63158ce71cd4cd4a744c51945","datavalue":{"value":{"entity-type":"item","numeric-id":1420598,"id":"Q1420598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b4e31afc53ed1877a153e555d6b18eccd763b24","datavalue":{"value":{"amount":"+0.8529713749885559","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":"Q1972147$FFEA51A9-4978-4B3A-AD18-0DC2F54BECF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a0aac243bf8ff5cc5080eb2b4818b19037b69ad","datavalue":{"value":{"entity-type":"item","numeric-id":4659585,"id":"Q4659585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0d8da0be4fd657b0b5d192a56257feeaf95fc00","datavalue":{"value":{"amount":"+0.7796099781990051","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":"Q1972147$E8731756-6303-4D8C-985C-6DBC623C3D78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7040bae7decb2f35c3bfbed82702e46898bd00c","datavalue":{"value":{"entity-type":"item","numeric-id":4526640,"id":"Q4526640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1efe243b9f8d5eab89cf778b7cd7704cf53321fb","datavalue":{"value":{"amount":"+0.7759275436401367","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":"Q1972147$D4B4EF6C-07FA-402B-A13F-50AA68035BF2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Higher edge-connectivities and tree decompositions in regular graphs","badges":[]}}}}}