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.
| Identifer | oai:union.ndltd.org:siu.edu/oai:opensiuc.lib.siu.edu:theses-3063 |
| Date | 01 December 2016 |
| Creators | Jayasooriya Arachchilage, Dinush Lanka Panditharathna |
| Publisher | OpenSIUC |
| Source Sets | Southern Illinois University Carbondale |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses |
Page generated in 0.0133 seconds