On constructive characterizations of (k,l)-sparse graphs

In this paper we study constructive characterizations of graphs satisfying tree-connectivity requirements. The main result is the following: if k and l are positive integers and l≤k2, then a necessary and sufficient condition is proved for a node being the last node of a construction in a graph having at most k|X|−(k+l) induced edges in every subset X of nodes. The arguments and proofs extend those of Frank and Szegő for the case l=1 [A. Frank, L. Szegő, Constructive characterizations on packing and covering by trees, Discrete Appl. Math. 131 (2) (2003) 347-371].