Embedding Complete Multipartite Graphs into Certain Trees

2019/10/22 by A. Arul Shantrinal, Shantrinal, A. Arul, R. Sundara Rajan +7
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1910.10643

openalex publication_date 2019/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

One of the important features of an interconnection network is its ability to efficiently simulate programs or parallel algorithms written for other architectures. Such a simulation problem can be mathematically formulated as a graph embedding problem. In this paper, we embed complete multipartite graphs into certain trees, such as k-rooted complete binary trees and k-rooted sibling trees.

Related

• Embedding complete multi-partite graphs into Cartesian product of paths and cycles
• Embedding onto Wheel-like Networks
• A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees
• Parallel Computation of Graph Embeddings
• A Topological Embedding of the Binary Tree into the Square Lattice