Induced subgraphs with maximum number of edges on crossed cubes
Y-Chuang Chen, Ya-Jyun Tian · 2009
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 Vmaxm(G), can be defined as Vmaxm(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.