Edge-Fault Tolerance of Hypercube-like Networks

Fault tolerance of an $(n,k)$-star network is measured by its $h$-super connectivity $\kappa_s^{(h)}$ or $h$-super edge-connectivity $\lambda_s^{(h)}$. Li {\it et al.} [Appl. Math. Comput. 248 (2014), 525-530; Math. Sci. Lett. 1 (2012), 133-138] determined $\kappa_s^{(h)}$ and $\lambda_s^{(h)}$ for $0\leq h\leq n-k$. This paper determines $\kappa_s^{(h)}=\lambda_s^{(h)}=\frac{(h+1)!(n-h-1)}{(n-k)!}$ for $n-k\leq h \leq n-2$.

The {\it crossing number} of a graph $G$ is the minimum number of pairwise intersections of edges in a drawing of $G$. The {\it $n$-dimensional folded hypercube} $FQ_n$ is a graph obtained from $n$-dimensional hypercube by adding all complementary edges. In this paper, we obtain upper and lower bounds of the crossing number of $FQ_n$.

This paper introduces a new variant of hypercubes, which we call Z-cubes. The n-dimensional Z-cube $H_n$ is obtained from two copies of the (n-1)-dimensional Z-cube $H_{n-1}$ by adding a special perfect matching between the vertices of these two copies of $H_{n-1}$. We prove that the n-dimensional Z-cubes $H_n$ has diameter $(1+o(1))n/\log_2 n$. This greatly improves on the previous known variants of hypercube of dimension n, whose diameters are all larger than n/3. Moreover,...

Let $S\subseteq V(G)$ and $\kappa_{G}(S)$ denote the maximum number $k$ of edge-disjoint trees $T_{1}, T_{2}, \cdots, T_{k}$ in $G$ such that $V(T_{i})\bigcap V(T_{j})=S$ for any $i, j \in \{1, 2, \cdots, k\}$ and $i\neq j$. For an integer $r$ with $2\leq r\leq n$, the {\em generalized $r$-connectivity} of a graph $G$ is defined as $\kappa_{r}(G)= min\{\kappa_{G}(S)|S\subseteq V(G)$ and $|S|=r\}$. The $r$-component connectivity $c\kappa_{r}(G)$ of a non-complete graph $G$ is ...

These lecture notes are on automorphism groups of Cayley graphs and their applications to optimal fault-tolerance of some interconnection networks. We first give an introduction to automorphisms of graphs and an introduction to Cayley graphs. We then discuss automorphism groups of Cayley graphs. We prove that the vertex-connectivity of edge-transitive graphs is maximum possible. We investigate the automorphism group and vertex-connectivity of some families of Cayley graphs th...

Vertex-fault-tolerance was introduced by Hayes~\cite{Hayes1976} in 1976, and since then it has been systematically studied in different aspects. In this paper we study $k$-vertex-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$, i.e., graphs in which removing any $k$ vertices leaves a graph that has $p$ disjoint complete graphs of order $c$ as a subgraph. The main contribution is to describe such graphs that have the smallest possible number of edges for $k...

The $n$-dimensional hypercube network $Q_n$ is one of the most popular interconnection networks since it has simple structure and is easy to implement. The $n$-dimensional locally twisted cube, denoted by $LTQ_n$, an important variation of the hypercube, has the same number of nodes and the same number of connections per node as $Q_n$. One advantage of $LTQ_n$ is that the diameter is only about half of the diameter of $Q_n$. Recently, some interesting properties of $LTQ_n$ we...

For a connected graph $\Gamma=(V,E)$, a subset $R$ of ordered vertices in $V$ is said to be a resolving set in $\Gamma$, if the vector of distances to the vertices in $R$ is unique for each $u^{i}\in V(\Gamma)$. The metric dimension of $\Gamma$ is the minimum cardinality of such a set $R$. If $R\setminus \{u^{i}\}$ is still a resolving set $\forall$ $u^{i}\in R$, then $R$ is called a fault-tolerant resolving set (FTRS) for $\Gamma$ and its least cardinality is the fault-toler...

For an interconnection network $G$, the {\it $\omega$-wide diameter} $d_\omega(G)$ is the least $\ell$ such that any two vertices are joined by $\omega$ internally-disjoint paths of length at most $\ell$, and the {\it $(\omega-1)$-fault diameter} $D_{\omega}(G)$ is the maximum diameter of a subgraph obtained by deleting fewer than $\omega$ vertices of $G$. The enhanced hypercube $Q_{n,k}$ is a variant of the well-known hypercube. Yang, Chang, Pai, and Chan gave an upper bou...

The hypercube Qn of dimension n is one of the most versatile and powerful interconnection networks. The n-dimensional folded cube denoted as FQn, a variation of the hypercube possesses some embeddable properties that the hypercube does not possess. Dong and Wang(In Theor. Comput. Sci.771(2019)93-98) conjectured that "A subset Em of edges of FQn is a perfect matching if and only if FQn - Em is isomorphic to Qn". In this paper, we disprove this conjecture by providing some perf...