Edge Partitions of Graphs by Trees
Dr. Grant Zhang
Department of Mathematical Sciences
November 13, 2009
219 Shelby Center
3:00 (Refreshements at 2:30)
We consider the minimum number tp(G) of subsets into which the edge set of a graph G can be partitioned so that each subset induces a tree. The problem of estimating tp(G) for a given graph is significant because trees are among the most cost-effective networks. For a connected graph G of order n, it is known that tp(G) ≤ (n + 1) / 2, and that tp(G) ≤ (n + 1) / 3 when G is triangle-free.
In this talk we show that if G is a Kt + 1-free and connected graph of order n, then
tp(G) ≤ n / 4 + 1 if t = 2
tp(G) ≤ [(t − 2)n / (2 t − 3)] + 1 if t = 3
where Kt + 1 denotes the complete graph of order t + 1. Graphs attaining the upper bound are completely characterized. In particular, when t = 2, our result proves a conjecture posed by M. Truszczynski in 1988, and by Q. Liu and D. B. West in 2008 independently.
- Hits: 90