A Study on Vertex Subset Degree Preserving Spanning Trees in Graphs

Abstract

Graph theory, because of its wide range of applications, it is now one of the fastest growing areas of mathematical research. Countless problems involving a collection of discrete objects can be phrased and solved by graph-theoretic methods. The versatility of graphs makes them indispensable tools in the design and analysis of communication networks, transportation networks etc. A spanning tree of a connected graph G is a tree in G, including all the vertices of G. These spanning trees play an important role in any network, as it maintains the connectivity of all the nodes with least number of edges. In certain fields of graph theory, it is often useful to find a minimum spanning tree of a weighted graph. In reality, some of the problems one encounter in applications cannot be solved by determining just any spanning tree; usually, the solution will have to satisfy some further restrictions. This leads to some other problems on spanning trees, including the degree-constrained spanning tree, the spanning tree with the fewest leaves and the diameter preserving spanning tree. These tree structures have many applications in telecommunications, computer networking, related domain in electric gas, and sewer networks; hence, they received the attention of many researchers. The objective of the thesis is to introduce a new class of spanning trees called, Vertex Subset Degree Preserving Spanning Trees in graphs and to analyze the idea under various directions. It includes existence conditions, generation of the trees, and enumeration of those trees and analysis of some associated parameters. Two applications of the newly defined classes of trees have also been explored. Vertex Degree Preserving Spanning Tree (v-DPST, where v is a vertex) is defined as a spanning tree T of G such that degT (v) = degG (v). A sufficient condition for every spanning tree to be v-DPST for some vertex in a simple connected graph is obtained. v-DPST is considered in digraphs and v-In Degree (Out Degree) Preserving Spanning In Trees (Out Trees) are defined; the existence conditions and the number of such spanning trees have been obtained. All spanning trees need not preserve the degree of any vertex in the graph. A graph in which each of its spanning trees is a v-DPST for some v V is defined as a Degree Preservable Graph. Various classes of graphs are analyzed and categorized as degree preservable and non-degree preservable. In a graph, a spanning tree can preserve the degrees of more than one vertex. So, Vertex Subset Degree Preserving Spanning Tree denoted by A-DPST, is defined as a spanning tree T such that degT(vi) = degG(vi), for all vi in A, which is a nonempty subset of the vertex set V of the graph G. The existence of the trees is analyzed and enumeration of A-DPST is also studied. Two different algorithms for generating such trees and an algorithm for generating all A-DPST in a weighted graph in increasing order of their weights are developed. A subset A of the vertex set V (G) is said to be Degree Preserving Spanning Tree (DPST)-set, if A-DPST exists. The upper and lower degree preserving numbers of a graph denoted by (G ) P  and P  (G) respectively are defined in terms of the cardinality of maximal DPST sets and analysis of them is done for some classes of graphs. Characterizations of graphs with some fixed (G ) P  are given. The upper degree preserving number for the complement graphs of some common families of graphs are obtained. The way of increasing (G ) P  for various classes of graphs is analyzed and construction of graphs with the degree preserving numbers is presented. DPST set in product graphs under tensor, cartesian and strong products is addressed. Decompositions of complete graphs and complete bipartite graphs into degree preserving spanning forest are carried out.