Department of
Applied
Mathematics

Generalizations of theorems of Nash-Williams and Hakimi on graph decompositions

Daqing Yang

Abstract

The fractional arboricity of a graph G, denoted by gamma_1(G), is defined as gamma_1(G) =max_{H subgraph of G, v(H)>1} e(H)/(v(H)-1). The celebrated Nash-Williams' Theorem states that a graph G can be decomposed into at most k forests if and only if gamma_1(G)<=k.

In this talk, we begin with the trying for some more generalized form of Nash-Williams' Theorem. To do this, we have generalized the fractional arboricity gamma_1(G) to the fractional i-arboricity gamma_i(G); and generalized the concepts of forests and trees to i-forest and i-trees. Then we prove that a graph G can be decomposed into k i-forests if and only if gamma_i(G)<=k.

Suppose P is a partition of V(G), for i>=1, let phi_i(G)=min_{|P|>i} (e(G/P)/(|P|-i). The also well-known Tutte's Theorem states that a graph G has k edge-disjoint spanning trees if and only if phi_1(G)>=k. We also prove that a graph G has k edge-disjoint i-trees if and only if phi_i(G)>=k. This generalizes Tutte's Theorem.

By beginning with Hakimi's Theorem on decomposing a graph into peudoforests, some similar generalizations along this line have also been tried.