## Abstract

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 τ(G). It is known that if G is connected then τ(G) ≤ ⌈|G|/2⌉. In this paper we show that if G is connected and has girth g ≥ 5 then τ(G) ≤ ⌊|G|/g⌋ + 1. Surprisingly, the case when g = 4 seems to be more difficult. We conjecture that in this case τ(G) ≤ ⌊|G|/4⌋ + 1 and show a wide class of graphs that 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 the weaker inequality τ(G) ≤ ⌊(|G| - 1)/3⌋ + 1.

Original language | English |
---|---|

Pages (from-to) | 273-286 |

Number of pages | 14 |

Journal | Periodica Mathematica Hungarica |

Volume | 19 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1988 |

## Keywords

- AMS (MOS) subject classifications (1980): Primary 05C70, Secondary 05C05
- bipartite graph
- Edge decomposition
- girth
- n-dimensional cube
- tree

## ASJC Scopus subject areas

- Mathematics (all)