DocumentCode :
1571252
Title :
Induced subgraphs with maximum number of edges on crossed cubes
Author :
Chen, V-Chuang ; Tian, Ya-Jyun
Author_Institution :
Dept. of Inf. Manage., Ming Hsin Univ. of Sci. & Technol., Hsinchu, Taiwan
fYear :
2009
Firstpage :
829
Lastpage :
832
Abstract :
In several parallel distributed processing systems, processors are connected on the basis of interconnection networks. The topological structure of an interconnection network can be modeled as a loopless undirected graph G = (V,E) where V is the vertex set and E the edge set of G. For a vertex subset V´ ¿ V of graph G, the subgraph of G induced by V´, denoted by G[V´], is a graph with vertex set V´ and all the edges of G with both ends of vertices in V´. An m-induced subgraph of a graph is such one which induced by m vertices. A maximum m-induced subgraph of a graph G, denoted by Vm max (G), can be defined as Vm max (G) = {G[V´] | maxV´Â¿V,|V´|=m |E(G[V´])|}. The results of maximum m-induced subgraph can be applied to the measurement of fault tolerance and bandwidth of networks, and also relate to electromechanical or optical sensors. Abdel-Ghaffar has shown the maximum m-induced subgraphs on the n-dimensional hypercubes in 2003. In this paper, we investigate in constructing the maximum m-induced subgraphs and working out the number of edges of the maximum m-induced subgraphs on the n-dimensional crossed cubes.
Keywords :
fault tolerance; graph theory; graphs; hypercube networks; multiprocessor interconnection networks; optical sensors; parallel processing; set theory; crossed cubes; edge set; electromechanical sensors; fault tolerance; induced subgraphs; interconnection networks; loopless undirected graph; network bandwidth; optical sensors; parallel distributed processing system; vertex set; Bandwidth; Bonding; Distributed processing; Fault tolerance; Graph theory; Hypercubes; Information management; Multiprocessor interconnection networks; Optical sensors; Out of order; crossed cube; induced subgraph; interconnection network; maximum m-induced subgraph;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Pervasive Computing (JCPC), 2009 Joint Conferences on
Conference_Location :
Tamsui, Taipei
Print_ISBN :
978-1-4244-5227-9
Electronic_ISBN :
978-1-4244-5228-6
Type :
conf
DOI :
10.1109/JCPC.2009.5420072
Filename :
5420072
Link To Document :
بازگشت