{"entities":{"Q580352":{"pageid":582119,"ns":120,"title":"Item:Q580352","lastrevid":49092745,"modified":"2026-01-06T14:17:20Z","type":"item","id":"Q580352","labels":{"en":{"language":"en","value":"The tree number of a graph with a given girth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016919"}},"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":"Q580352$92A462C9-CD3F-479B-86E7-6A1EA6EB23D6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3572724b52384838e39591f6009e7eaff3506605","datavalue":{"value":{"text":"The tree number of a graph with a given girth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q580352$339F8481-C720-44F6-A08D-2A9AF017C316","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c0fe5636ce6f03ff9f7bcbbb9f3d0f30cb1faee9","datavalue":{"value":"0626.05014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580352$7A880F01-492C-4C48-A824-B16EEC5EF80D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a56c002f80949422fc035b43d1d93e1a1ad9c420","datavalue":{"value":"10.1007/BF01848836","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580352$71ED30BA-4C3F-4462-ACAF-84BEC2EED66A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"615950119797f35f49728e278e9727b73c5c7f8e","datavalue":{"value":{"entity-type":"item","numeric-id":168620,"id":"Q168620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580352$DDA97235-BDDB-4B37-89E9-BF8063373B44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q580352$043E0721-CE7C-4128-B1A1-F8F222A2BE87","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5cef4f6caae0bea0a4c1c4d40d9fe63b953b19a0","datavalue":{"value":"A family of subtrees of a graph G whose edge sets form a partition of the edge set of G is called a tree decomposition of G. The minimum number of trees in a tree decomposition of G is called the tree number of G and is denoted by \\(\\tau\\) (G). It is known that if G is connected then \\(\\tau\\) (G)\\(\\leq \\lceil | G| /2\\rceil\\). In this paper we show that if G is connected and has girth \\(g\\geq 5\\) then \\(\\tau (G)\\leq \\lfloor | G| /g\\rfloor +1\\). Surprisingly, the case when \\(g=4\\) seems to be more difficult. We conjecture that in this case \\(\\tau (G)\\leq \\lfloor | G| /4\\rfloor +1\\) and show a wide class of graphs which satisfy it. Also, some special graphs like complete bipartite graphs and n- dimensional cubes for which we determine their tree numbers satisfy it. In the general case we prove a weaker inequality \\(\\tau (G)\\leq \\lfloor | G| -1)/3\\rfloor +1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q580352$E8E44A47-7A29-4425-BF84-E06C6F63C26D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580352$6FE969C4-0054-4061-9638-BF6E2CF4C30C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580352$230FC521-B8F6-4C69-A2C3-F153A3360151","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"56fc0ef1427778c6b8220c95e4abad2b817bc19b","datavalue":{"value":"4016919","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580352$24FE1DA5-526D-4D01-AF1F-9A1B120106BB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f1e625afea5b1a633df9fe58ad43c2d03e075ec","datavalue":{"value":"tree decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q580352$15B6785A-F851-40D5-A8B2-4DB37C86EAE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8d40e121a3b35ac826d07dbeec05a5a495116a9","datavalue":{"value":"tree number","type":"string"},"datatype":"string"},"type":"statement","id":"Q580352$90ABE012-7906-4072-8B65-346D177017F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q580352$5C5607DE-C72E-488E-8458-66591624F3F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"912d85dc638926e5499324084c23bda3fb1385f2","datavalue":{"value":"complete bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q580352$405C5ECF-18E5-4031-AC15-5791108832B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c54bc3cd070e2fab66d4476351480bd5110ce6b","datavalue":{"value":"n- dimensional cubes","type":"string"},"datatype":"string"},"type":"statement","id":"Q580352$88E9DE79-FCC1-41C2-A3EF-C83A45C0A1BE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca2007526997750f6621dbd8268e4738be04df24","datavalue":{"value":{"entity-type":"item","numeric-id":286082,"id":"Q286082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580352$FA3C2222-85DA-4A85-ADA0-9EC87D1B7A1D","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":"Q580352$D986D333-0469-4232-B8A9-446A886B7966","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"249a26ceb3aa2f9c2ec362d3d136ce7122071986","datavalue":{"value":{"entity-type":"item","numeric-id":1250826,"id":"Q1250826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580352$6604ECA1-9880-47E1-B1DA-894A3356F257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b08ae538a74fbbd6e523599210fae6d0d8892f04","datavalue":{"value":{"entity-type":"item","numeric-id":3915022,"id":"Q3915022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580352$D312A57A-4A65-4D25-88E1-367D9D2308A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"626770cd323c5d7b2407af684ff2ab4356da4328","datavalue":{"value":{"entity-type":"item","numeric-id":3703914,"id":"Q3703914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580352$03B62CBB-BA86-4953-89AD-9345F60F4495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d1474ad965005531fc787ddda571bd10843eacd","datavalue":{"value":{"entity-type":"item","numeric-id":3853641,"id":"Q3853641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580352$19A2B161-2292-4FD8-8D4B-62F83A0461D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d5c6acfb4e4d1571206354c69fe79011465b8da","datavalue":{"value":{"entity-type":"item","numeric-id":5548205,"id":"Q5548205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580352$54074012-1BC6-42E4-B586-8D16E97FE571","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79f40f6cac0c780a9b93fef04ad01fbee5da55dc","datavalue":{"value":{"entity-type":"item","numeric-id":5731396,"id":"Q5731396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580352$FA75EF8F-0EBF-4423-8B19-C0127F0DEC86","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0e75023ebfd50a1c647edc44051b1b9154ba9ed8","datavalue":{"value":"https://doi.org/10.1007/bf01848836","type":"string"},"datatype":"url"},"type":"statement","id":"Q580352$8E8CEA65-4B78-4931-B057-BC736B5D8404","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"baca858ce28cab3dc964c62b492029bd5eba4718","datavalue":{"value":"W2029657243","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580352$9F8DD3D6-D713-4126-BFA7-BCBB9797A91D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"362f3bb23c9792c98becc8b5a129ad15f2384db5","datavalue":{"value":{"entity-type":"item","numeric-id":1010820,"id":"Q1010820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e426de40ed556c688311429a5bc1b4c8d445c9f","datavalue":{"value":{"amount":"+0.8086104989051819","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":"Q580352$57FFCD82-104F-40F4-A685-4A290CD82D12","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":"814f4c1e40fd0637fb6d316952e419061cde1b22","datavalue":{"value":{"amount":"+0.7948686480522156","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":"Q580352$95A5FC66-913A-4130-8025-997EE08A2856","rank":"normal"},{"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":"7d92abf206426cf7ef9c04ae1cc40b773f5c8e19","datavalue":{"value":{"amount":"+0.791995108127594","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":"Q580352$75FFAAB6-A0E0-4939-AABD-9AB6FCAC1952","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dde9ac7ceb5ea125203c0f4803b6bd3b6553f234","datavalue":{"value":{"entity-type":"item","numeric-id":1569062,"id":"Q1569062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38e581851a4c529e129d049d7ad45bd6d950993b","datavalue":{"value":{"amount":"+0.785595178604126","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":"Q580352$55F77363-C31F-4EA3-8CA1-DD79AFEA5470","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96cc5f85139fd08c30e88105efa6aa58ed40e0c5","datavalue":{"value":{"entity-type":"item","numeric-id":1850563,"id":"Q1850563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1d67f754218c5a912d9ee5a8360c04826bd25c4","datavalue":{"value":{"amount":"+0.7797173857688904","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":"Q580352$16A07BAC-24FA-4C0C-B142-17C24095907F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:580352","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:580352"}}}}}