One of the important issues in evaluating an interconnection network is to study the fault-tolerant Hamiltonian cycle and Hamiltonian path embedding problems. The$k$-ary$n$-cube (denoted by$Q^{k}_{n}$) networks are used as interconnection networks for many parallel and distributed computing systems. In this article, we investigate the Hamiltonian cycle and path embeddings in the bipartite$k$-ary$n$-cube$Q^{k}_{n}$based on$K_{1,1}$-structure faults. We show that there exists a Hamiltonian cycle in$Q^{k}_{n}-\mathcal {F}$if$|\mathcal {F}|\leq 2n-2$and there exists a Hamiltonian path between any two vertices from different partite sets in$Q^{k}_{n}-\mathcal {F}$if$|\mathcal {F}|\leq 2n-3$for$n\geq 2$and even$k\geq 4$, where$\mathcal {F}$is a set of vertex-disjoint subgraphs isomorphic to$K_{1,1}$in$Q_{n}^{k}$. In some sense, the results mean that when a subset$S$of at most$4n-4$(resp.$4n-6$) processors is deleted from a bipartite$Q^{k}_{n}$, there exists a Hamiltonian cycle (resp. a Hamiltonian path between any two healthy processors from different partite sets) in the remaining network. Our results, in some sense, compensate the results in Lv et al. [J. Parallel Distrib. Comput., 120, 148–158, 2018] and [Comput. J., 60, 159–179, 2017], where authors studied the$K_{1,3}$-substructure fault-tolerant Hamiltonian cycle and path embedding problems in nonbipartite$k$-ary$n$-cubes. In comparison, the bipartite$k$-ary$n$-cube$Q^{k}_{n}$can keep the same$K_{1,1}$-structure fault-tolerant Hamiltonian capabilities as the nonbipartite one.

Abstract The conditional edge-connectivity is an important parameter to evaluate the reliability and fault tolerance of multi-processor systems. The $n$-dimensional bijective connection networks $B_{n}$ contain hypercubes, crossed cubes, Möbius cubes and twisted cubes, etc. The conditional edge-connectivity of a connected graph $G$ is the minimum cardinality of edge sets, whose deletion disconnects $G$ and results in each remaining component satisfying property $\mathscr{P}$. And let $F$ be the edge set as desired. For a positive integer $a$, if $\mathscr{P}$ denotes the property that the average degree of each component of $G-F$ is no less than $a$, then the conditional edge-connectivity can be called the $a$-average degree edge-connectivity $\overline{\lambda }_{a}(G)$. In this paper, we determine that the exact value of the $a$-average degree edge-connectivity of an $n$-dimensional bijective connection network $\overline{\lambda }_{a}(B_{n})$ is $(n-a)2^a$ for each $0\leq a \leq n-1 $ and $n\geq 1$. 1

Abstract Motivated by effects caused by structure link faults in networks, we study the following graph theoretical problem. Let $T$ be a connected subgraph of a graph $G$ except for $K_{1}$. The $T$-structure edge-connectivity $\lambda (G;T)$ (resp. $T$-substructure edge-connectivity $\lambda ^s(G;T)$) of $G$ is the minimum cardinality of a set of edge-disjoint subgraphs $\mathcal{F}=\{T_{1},T_{2},\ldots ,T_{m}\}$ (resp. $\mathcal{F}=\{T_{1}^{^{\prime}},T_{2}^{^{\prime}},\ldots ,T_{m}^{^{\prime}}\}$) such that $T_{i}$ is isomorphic to $T$ (resp. $T_{i}^{^{\prime}}$ is a connected subgraph of $T$) for every $1 \le i \le m$, and $E(\mathcal{F})$’s removal leaves the remaining graph disconnected. In this paper, we determine both $\lambda (G;T)$ and $\lambda ^{s}(G;T)$ for $(1)$ the hypercube $Q_{n}$ and $T\in \{K_{1,1},K_{1,2},K_{1,3},P_{4},Q_{1},Q_{2},Q_{3}\}$; $(2)$ the $k$-ary $n$-cube $Q^{k}_{n}$ $(k\ge 3)$ and $T\in \{K_{1,1},K_{1,2},K_{1,3},Q^{3}_{1},Q^{4}_{1}\}$; $(3)$ the balanced hypercube $BH_{n}$ and $T\in \{K_{1,1},K_{1,2},BH_{1}\}$. We also extend some known results.

Abstract Diagnosability and connectivity are important metrics for the reliability and fault diagnosis capability of interconnection networks, respectively. The g-extra connectivity of a graph G, denoted by $\kappa _g(G)$, is the minimum number of vertices whose deletion will disconnect the network and every remaining component has more than $g$ vertices. The g-extra conditional diagnosability of graph G, denoted by $t_g(G)$, is the maximum number of faulty vertices that the graph G can guarantee to identify under the condition that every fault-free component contains at least g+1 vertices. In this paper, we first determine that g-extra connectivity of DQcube is $\kappa _g(G)=(g+1)(n+1)-\frac{g(g+3)}{2}$ for $0\leq g\leq n-3$ and then show that the g-extra conditional diagnosability of DQcube under the PMC model $(n\geq 4, 1\leq g\leq n-3)$ and the MM$^\ast$ model $(n\geq 7, 1\leq g\leq \frac{n-3}{4})$ is $t_g(G)=(g+1)(n+1)-\frac{g(g+3)}{2}+g$, respectively.

The underlying topology of an interconnection network can be modeled by a digraph D=(V,A)⁠. A strongly connected digraph D is maximally arc-connected if its arc-connectivity is equal to its minimum degree. The maximally arc-connected tolerance mλ(D) to arc-faults of a maximally arc-connected digraph D is the maximum integer f, for which D−S is still maximally arc-connected for any set S⊆A(D) with |S|≤f⁠. The index mλ(D) is used to measure the reliability of networks. In this paper, we present upper and lower bounds on mλ(D)⁠. More refined bounds are obtained under some conditions, from which the exact values of mλ(D) are determined for some networks modeled by digraphs.