The tree number of a graph with a given girth
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\).
- Decomposition of Finite Graphs Into Forests
- scientific article; zbMATH DE number 3654142 (Why is no real title available?)
- scientific article; zbMATH DE number 3726401 (Why is no real title available?)
- scientific article; zbMATH DE number 3262259 (Why is no real title available?)
- On partitions of graphs into trees
- The linear arboricity of some regular graphs
- Tree-thickness and caterpillar-thickness under girth constraints
- On the tree number of regular graphs
- Minimum degree and minimum number of edge-disjoint trees
- On a conjecture about trees in graphs with large girth
- scientific article; zbMATH DE number 5305008 (Why is no real title available?)
- The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
This page was built for publication: The tree number of a graph with a given girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q580352)
