Browsing by Author "Woudaj, Hailemichael"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    On Counting Spanning Trees of the Graph
    (Addis Ababa University, 2011-01) Woudaj, Hailemichael; Tsegaye, Yirgalm (PhD)
    In this paper, we will observe how to find the spanning trees of a graph and the methods that we use to calculate. The methods that we use for calculating the spanning tree of the graph are deletion and contraction, matrix tree theorem and combinatorial interpretation of matrix tree theorem. In the matrix tree theorem we will explore an interesting relationship between linear algebra and graphs. In combinatorial interpretation we develop a new approach by constructing the polynomial that enumerates the spanning trees of the graph according to degrees of all vertices. The matrix tree theorem does not give the final answer to all problems concerning enumeration of trees because finding the determinant of a matrix is a complicated task for complicated graphs. So, this paper is useful to find the number of spanning trees of the complicated graph simply