On vertex subset degree preserving spanning trees

Spanning trees play an important role in networks. There are many kinds of spanning trees in the literature. A new class of spanning trees called Vertex Subset Degree Preserving Spanning Tree (A-DPST) is defined as a spanning tree T of the graph G(V,E) such that deg_T(v_i) = deg_G(v_i) for all v_i in A which is a nonempty subset of V[1]. A-DPST's are having applications in networks. Especially when A is the singleton set corresponding to a router of a network then any spanning tree of the network is a A-DPST. The necessary and sufficient condition for the existence of such trees and some results relating to A-DPST were obtained in [1]. In this paper two more characterizations of such trees are presented. The bounds for the cardinality _ΨAof the subset A, for some common families of graphs are found. A procedure for counting such A-DPST in a graph if it exists is given which is the main result because counting plays important role in network theory. The algorithms for generating such trees, finding upper bound for the cardinality of A in a general graph are also included. The analyses of their time complexity are also included.