On the P − vertex spanning subtree polytope of a graph

In this paper, given an undirected graph G = (V,E), with |V | = n, we introduce a new integer linear description of the polytope PT (G) of p−vertex spanning subtrees of G. A p−vertex spanning subtree is a subtree that spans p < n vertices of G. Unlike existing linear descriptions of such a polytope, ours is only defined on the space of variables associated with edges of G and is based on well known partition inequalities. After, we address constructive algorithms generating p − vertex spanning subtrees that incidence vectors are affinely independent to determine the dimension of PT(G)and to show the facetness of trivial inequalitiesxe ≥ 0 and xe ≤ 1.