Edge Partitions of Graphs by Trees

Dr. Grant Zhang

Department of Mathematical Sciences
UAHuntsville

November 13, 2009
219 Shelby Center
3:00 (Refreshements at 2:30)

Abstract

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 K_{t + 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 K_{t + 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.