2015/11/05 by Reddy, K. Krishna Mohan, Renjith, P., Sadagopan, N.
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1511.01696
For a connected labelled graph G, a \em spanning tree T is a connected and an acyclic subgraph that spans all vertices of G. In this paper, we consider a classical combinatorial problem which is to list all spanning trees of G. A Halin graph is a graph obtained from a tree with no degree two vertices and by joining all leaves with a cycle. We present a sequential and parallel algorithm to enumerate all spanning trees in Halin graphs. Our approach enumerates without repetitions and we make use of O((2pd)p) processors for parallel algorithmics, where d and p are the depth, the number of leaves, respectively, of the Halin graph. We also prove that the number of spanning trees in Halin graphs is O((2pd)p).