Date of Award


Degree Name

Master of Science



First Advisor

McSorley, John


A Spanning tree of a graph G is a subgraph that is a tree which concludes all of the vertices of G. And a graph G is bipartite if the vertex set of G can be partitioned in to two sets A and B, such that every edge of G joins a vertex of A and a vertex of B. We can see that every tree(including spanning tree) is bipartite. We define type of a spanning tree using this idea as follows: We divide vertices of a spanning trees in to two partitions A and B by using its bipartition. Then, we define type of the spanning tree by (| A |, | B |), provided | A | less than or equal to | B |. We first identify the characteristics for a graph to have a spanning trees of a certain type. Then, implement some theorems about the type.




This thesis is only available for download to the SIUC community. Others should
contact the interlibrary loan department of your local library.