Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userReliability evaluation of folded hypercubes in terms of component connectivity
125
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The component connectivity is the generalization of connectivity which is an parameter for the reliability evaluation of interconnection networks. The $g$-component connectivity $ckappa_{g}(G)$ of a non-complete connected graph $G$ is the minimum number of vertices whose deletion results in a graph with at least $g$ components. The results in [Component connectivity of the hypercubes, International Journal of Computer Mathematics 89 (2012) 137-145] by Hsu et al. determines the component connectivity of the hypercubes. As an invariant of the hypercube, we determine the $(g+1)$-component connectivity of the folded hypercube $ckappa_{g}(FQ_{n})=g(n+1)-frac{1}{2}g(g+1)+1$ for $1leq g leq n+1, ngeq 8$ in this paper.
rate research
Read More
As a generalization of vertex connectivity, for connected graphs $G$ and $T$, the $T$-structure connectivity $kappa(G, T)$ (resp. $T$-substructure connectivity $kappa^{s}(G, T)$) of $G$ is the minimum cardinality of a set of subgraphs $F$ of $G$ that each is isomorphic to $T$ (resp. to a connected subgraph of $T$) so that $G-F$ is disconnected. For $n$-dimensional hypercube $Q_{n}$, Lin et al. [6] showed $kappa(Q_{n},K_{1,1})=kappa^{s}(Q_{n},K_{1,1})=n-1$ and $kappa(Q_{n},K_{1,r})=kappa^{s}(Q_{n},K_{1,r})=lceilfrac{n}{2}rceil$ for $2leq rleq 3$ and $ngeq 3$. Sabir et al. [11] obtained that $kappa(Q_{n},K_{1,4})=kappa^{s}(Q_{n},K_{1,4})=lceilfrac{n}{2}rceil$ for $ngeq 6$, and for $n$-dimensional folded hypercube $FQ_{n}$, $kappa(FQ_{n},K_{1,1})=kappa^{s}(FQ_{n},K_{1,1})=n$, $kappa(FQ_{n},K_{1,r})=kappa^{s}(FQ_{n},K_{1,r})=lceilfrac{n+1}{2}rceil$ with $2leq rleq 3$ and $ngeq 7$. They proposed an open problem of determining $K_{1,r}$-structure connectivity of $Q_n$ and $FQ_n$ for general $r$. In this paper, we obtain that for each integer $rgeq 2$, $kappa(Q_{n};K_{1,r})=kappa^{s}(Q_{n};K_{1,r})=lceilfrac{n}{2}rceil$ and $kappa(FQ_{n};K_{1,r})=kappa^{s}(FQ_{n};K_{1,r})= lceilfrac{n+1}{2}rceil$ for all integers $n$ larger than $r$ in quare scale. For $4leq rleq 6$, we separately confirm the above result holds for $Q_n$ in the remaining cases.
The $g$-component edge connectivity $clambda_g(G)$ of a non-complete graph $G$ is the minimum number of edges whose deletion results in a graph with at least $g$ components. In this paper, we determine the component edge connectivity of the folded hypercube $clambda_{g+1}(FQ_{n})=(n+1)g-(sumlimits_{i=0}^{s}t_i2^{t_i-1}+sumlimits_{i=0}^{s} icdot 2^{t_i})$ for $gleq 2^{[frac{n+1}2]}$ and $ngeq 5$, where $g$ be a positive integer and $g=sumlimits_{i=0}^{s}2^{t_i}$ be the decomposition of $g$ such that $t_0=[log_{2}{g}],$ and $t_i=[log_2({g-sumlimits_{r=0}^{i-1}2^{t_r}})]$ for $igeq 1$.
The generalized $k$-connectivity of a graph $G$, denoted by $kappa_k(G)$, is a generalization of the traditional connectivity. It is well known that the generalized $k$-connectivity is an important indicator for measuring the fault tolerance and reliability of interconnection networks. The $n$-dimensional folded hypercube $FQ_n$ is obtained from the $n$-dimensional hypercube $Q_n$ by adding an edge between any pair of vertices with complementary addresses. In this paper, we show that $kappa_3(FQ_n)=n$ for $nge 2$, that is, for any three vertices in $FQ_n$, there exist $n$ internally disjoint trees connecting them.
As a generalization of the traditional connectivity, the g-component edge connectivity c{lambda}g(G) of a non-complete graph G is the minimum number of edges to be deleted from the graph G such that the resulting graph has at least g components. Hypercube-like networks (HL-networks for short) are obtained by manipulating some pairs of edges in hypercubes, which contain several famous interconnection networks such as twisted cubes, Mobius cubes, crossed cubes, locally twisted cubes. In this paper, we determine the (g + 1)-component edge connectivity of the n-dimensional HL-networks.
We introduce the notion of a symmetric basis of a vector space equipped with a quadratic form, and provide a sufficient and necessary condition for the existence to such a basis. Symmetric bases are then used to study Cayley graphs of certain extraspecial 2-groups of order 2^{2r+1} (rgeq 1), which are further shown to be normal Cayley graphs and 2-arc-transitive covers of 2r-dimensional hypercubes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
