Journal of Interconnection Networks

This paper introduces a type of graph embedding called a mutual embedding. A mutual embedding between two n-node graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ is an identification of the vertices of V₁ and V₂, i.e., a bijection $\pi :V_1\to V_2$, together with an embedding of G₁ into G₂ and an embedding of G₂ into G₁ where in the embedding of G₁ into G₂, each node u of G₁ is mapped to π(u) in G₂ and in the embedding of G₂ into G₁ each node v of G₂ is mapped to ${\pi }^{-1}\left(v\right)$ in G₁. The identification of vertices in G₁ and G₂ constrains the two embeddings so that it is not always possible for both to exhibit small congestion and dilation, even if there are traditional one-way embeddings in both directions with small congestion and dilation. Mutual embeddings arise in the context of finding preconditioners for accelerating the convergence of iterative methods for solving systems of linear equations. We present mutual embeddings between several types of graphs such as linear arrays, cycles, trees, and meshes, prove lower bounds on mutual embeddings between several classes of graphs, and present some open problems related to optimal mutual embeddings.

Let F_v (resp. F_e) be the set of faulty vertices (resp. faulty edges) in the n-dimensional balanced hypercube BH_n. The edge-bipancyclicity of BH_n − F_v for |F_v| ≤ n − 1 had been proved in [Inform. Sci. 288 (2014) 449–461]. The existence of edge-Hamiltonian cycles in BH_n − F_e for |F_e| ≤ 2n − 2 were obtained in [Appl. Math. Comput. 244 (2014) 447–456]. In this paper, we consider fault-tolerant cycle embedding of BH_n with both faulty vertices and faulty edges, and prove that there exists a fault-free cycle of length 2²ⁿ − 2|F_v| in BH_n with |F_v| + |F_e| ≤ 2n − 3 and |F_v| ≤ n − 1 for n ≥ 2.

Two important components that consume the majority of IT power in data centers are the servers and the Data Center Network (DCN). Existing works fail to fully utilize power management techniques on the servers and in the DCN at the same time. In this paper, we jointly consider VM placement on servers with scalable frequencies and flow scheduling in the DCN, to minimize the overall system’s power consumption. Due to the convex relation between a server’s power consumption and its operating frequency, we prove that, given the number of servers to be used, computation workloads should be allocated to severs in a balanced way, to minimize the power consumption on servers. To reduce the power consumption of the DCN, we further consider the flow requirements among the VMs during VM allocation and assignment. Also, after VM placement, flow consolidation is conducted to reduce the number of active switches and ports. We notice that, choosing the minimum number of servers to accommodate the VMs may result in high power consumption on servers, due to servers’ increased operating frequencies. Choosing the optimal number of servers purely based on servers’ power consumption leads to reduced power consumption on servers, but may increase power consumption of the DCN. We propose to choose the optimal number of servers to be used, based on the overall system’s power consumption. Simulations show that, our joint power optimization method helps to reduce the overall power consumption significantly, and outperforms various existing state-of-the-art methods in terms of reducing the overall system’s power consumption.

A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least one vertex in each other color classes. The b-chromatic number of a graph G, denoted by $\phi \left(G\right)$, is the maximal integer k such that G has a b-coloring with k colors. In this paper, the b-chromatic numbers of the coronas of cycles, star graphs and wheel graphs with different numbers of vertices, respectively, are obtained. Also the bounds for the b-chromatic number of corona of any two graphs is discussed.

Fault diagnosis is important for the reliability of interconnection networks. This paper addresses the fault diagnosis of n-dimensional pancake graph P_n under the comparison diagnosis model. By the concept of local diagnosability, we first prove that the diagnosabitly of P_n is n − 1, and it has strong local diagnosability property even if there are n − 3 faulty edges. Furthermore, we present efficient algorithms to locate extended star and Hamiltonian path structures in P_n, respectively. According to the works of Li et al. and Lai, the extended star and Hamiltonian path structures can be used to identify all faulty vertices in linear time, provided the number of faulty vertices is no more than n − 1.

The hypercubic family of interconnection networks, encompassing the hypercube and its derivatives and variants, has a wide range of applications in parallel processing. Various problems in general complex networks can be addressed by choosing a hypercubic network as a skeleton. In this paper, we provide insight into why hypercubic networks are suitable as network skeletons and discuss a mapping scheme to take advantage of the symmetry of such networks for developing efficient algorithms.

We propose the complete cubic network structure to extend the existing class of hierarchical cubic networks, and establish a general connectivity result which states that the surviving graph of a complete cubic network, when a linear number of vertices are removed, consists of a large (connected) component and a number of smaller components which altogether contain a limited number of vertices.

As applications, we characterize several fault-tolerance properties for the complete cubic network, including its restricted connectivity, i.e., the size of a minimum vertex cut such that the degree of every vertex in the surviving graph has a guaranteed lower bound; its cyclic vertex-connectivity, i.e., the size of a minimum vertex cut such that at least two components in the surviving graph contain a cycle; its component connectivity, i.e., the size of a minimum vertex cut whose removal leads to a certain number of components in its surviving graph; and its conditional diagnosability, i.e., the maximum number of faulty vertices that can be detected via a self-diagnostic process, in terms of the common Comparison Diagnosis model.

Motivated by the concept of reverse signed domination, we introduce the reverse minus domination problem on graphs, and study the reverse minus and signed domination problems from the algorithmic point of view. In this paper, we show that both the reverse minus and signed domination problems are polynomial-time solvable for strongly chordal graphs and distance-hereditary graphs, and are linear-time solvable for trees. For chordal graphs and bipartite planar graphs, however, we show that the decision problem corresponding to the reverse minus domination problem is NP-complete. For doubly chordal graphs and bipartite planar graphs, we show that the decision problem corresponding to the reverse signed domination problem is NP-complete. Furthermore, we show that even when restricted to bipartite planar graphs or doubly chordal graphs, the reverse signed domination problem is not fixed parameter tractable.