Characterizations of arboricity of graphs.

Abstract

The aim of this paper is to give several characterizations for the following two classes of graphs: (i) graphs for which adding any l edges produces a graph which is decomposible into k spanning trees and (ii) graphs for which adding some l edges produces a graph which is decomposible into k spanning trees. Introduction and Theorems The concept of decomposing a graph into the minimum number of trees or forests dates back to Nash-Williams and Tutte [6, 7, 11]. Since then, many authors have examined various tree decompositions of classes of graphs (for example [2, 8]). The aim of this paper is to give several characterizations for