Embedding of Petersen Graphs into Certain Trees

Jasintha Quadras and S. Sarah Surya

Department of Mathematics, Stella Maris College, Chennai, INDIA


The study of graph embedding is an important topic in the theory of parallel computation. The existence of such an embedding demonstrates the ability of a parallel computer whose interconnection network is described by a guest graph. The Petersen graph is certainly one of the most famous objects that graph theorists have come across. In this paper, we present an algorithm for finding the exact wirelength of the Petersen graph P(n, 1), i.e. the circular ladder into the k-rooted complete binary trees and binomial trees and prove its correctness using the Congestion lemma and Partition lemma.

Keywords :circular ladder, k-rooted complete binary tree, binomial trees, wirelength, edge congestion

map1 map2 map3