Embedding Cartesian Product Graphs into Cayley Graphs
Zhao Jing Meng · Chinese Journal of Computers · 2000
Finding a good topology for multiprocessor interconnected network is a problem that is widely discussed recently, and many topologies have been recommended, such as hypercube, generalized hypercube and the recently proposed class of graphs——Cayley Graphs, among which is star graph, which is looked on as an attractive alternative to hypercube. One problem in dealing with the newly proposed topology is the lack of algorithms tailored for them, which impede the application of these network topologies. In order to solve this problem, embeddings of graphs are considered. With the embedding of one graph into another, the host can employ algorithms proposed for the guest. However, in the previous efforts, only the embeddings of some particular graphs were discussed. In this paper, the general method of embedding a kind of graphs, Cartesian product graphs, into another kind of graphs, Cayley graphs, is presented. These embeddings are carried out by first embed the factor graphs of the Cartesian product graphs into the hosts, then take the products, which is a concept introduced in this paper, of these factor embeddings. A theorem is given which presents a method to compute the dilation of the product embedding from the properties of the “factor embeddings”.