Counting spanning binary trees of labelled undirected graphs

Abstract

The number of spanning binary trees of a connected labelled undirectedgraph is an important quantity which is closely related to the reliability of thegraph as a network. Many problems and their applications in mathematics andnetworking are based on spanning trees and binary trees of the graph. However,explicitly determining the number of spanning binary trees in networks is atheoretical challenge. Here we extend Prufer�s method of one to one correspondencebetween prufer sequences and spanning trees of complete graph to countthe spanning binary trees of arbitrary graphs. We follow a two step approach tocount the number of spanning binary trees of an arbitrary connected graph on0n0 vertices. We also exploit the technique of edge contraction and find some fastmethods for converting a simple connected graph into a complete graph whichenables us to count the spanning trees of the given graph.