On Counting Spanning Trees of the Graph

No Thumbnail Available

Date

2011-01

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

Citation

Collections