On Counting Spanning Trees of the Graph
No Thumbnail Available
Date
2011-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
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
Description
Keywords
On Counting Spanning