Structure connectivity and substructure connectivity are innovative indicators for assessing network reliability and fault tolerance. Similarly, fault diameter evaluates fault tolerance and transmission delays in networks. This paper extends the concept of fault diameter by introducing two new variants: structure fault diameter and substructure fault diameter, derived from structure connectivity and substructure connectivity respectively. For a connected graph $G$ with $W$-structure connectivity $κ(G;W)$ or $W$-substructure connectivity $κ^s(G;W)$, the $W$-structure fault diameter $D_f(G;W)$ and $W$-substructure fault diameter $D_f^s(G;W)$ are defined as the maximum diameter of any subgraph of $G$ resulting from removing up to $κ(G;W)-1$ $W$-structures or $κ^s(G;W)-1$ $W$-substructures. For the $n$-dimensional hypercube $Q_n$ with $n \geq 3$ and $1 \leq m \leq n - 2$, we determine both $D_f(Q_n;Q_m)$ and $D_f^s(Q_n;Q_1)$. These findings generalize existing results for the diameter and fault diameter of $Q_n$, providing a broader understanding of the hypercube's structural properties under fault conditions.

The generalized hypercube G ( m 1 , m 2 , … , m n ) is one of the key interconnection networks with attractive topological properties. In this paper, we focus our attention on the super spanning connectivity of G ( m 1 , m 2 , … , m n ) . We show that for a pair of arbitrary nodes x and y in G ( m 1 , m 2 , … , m n ) ( m i ≥ 3 , i = 1 , 2 , … , n ) , there is a set of s ( 1 ≤ s ≤ κ ( G ( m 1 , m 2 , … , m n ) ) ) internally node-disjoint x , y -paths whose union covers every vertex in G ( m 1 , m 2 , … , m n ) , where κ ( G ( m 1 , m 2 , … , m n ) ) denotes the connectivity of G ( m 1 , m 2 , … , m n ) . Our results, in some sense, extended a previous result in Shih and Kao (2011) [23] .

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 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.