The tree number of a graph with a given girth (Q580352): Difference between revisions

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\).