Wirelength of embedding complete multipartite graphs into certain graphs.

Graph embedding is an important technique that maps a guest graph into a host graph, usually an interconnection network. Many applications can be modeled as graph embedding. In architecture simulation, graph embedding has been known as a powerful tool for implementation of parallel algorithms or simulation of different interconnection networks. The quality of an embedding can be measured by certain cost criteria. One of these criteria is the wirelength and has been well studied by many authors (Lai and Tsai, 2010 18 ; Fan and Jia, 2007 10 ; Han et al., 2010 15 ; Fang and Lai, 2005 11 ; Park and Chwa, 2000 23 ; Rajasingh et al., 2004; Yang et al., 2010; Yang, 2009 27 ; Manuel et al., 2009; Bezrukov et al., 1998; Rostami and Habibi, 2008 26 ; Choudum and Nahdini, 2004 7 ; Guu, 1997 14). In this paper, we compute the exact wirelength of embedding complete multipartite graphs into certain graphs, such as path, cycle, wheel, hypertree, cylinder, torus and 3-regular circulant graphs. [ABSTRACT FROM AUTHOR]