Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComponent edge connectivity of the folded hypercube
67
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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.
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.
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.
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.
An edge-ordering of a graph $G=(V,E)$ is a bijection $phi:Eto{1,2,...,|E|}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,...,e_k$ is an increasing path if it is a path in $G$ which satisfies $phi(e_i)<phi(e_j)$ for all $i<j$. For a graph $G$, let $f(G)$ be the largest integer $ell$ such that every edge-ordering of $G$ contains an increasing path of length $ell$. The parameter $f(G)$ was first studied for $G=K_n$ and has subsequently been studied for other families of graphs. This paper gives bounds on $f$ for the hypercube and the random graph $G(n,p)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
