اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe generalized 3-connectivity of the folded hypercube $FQ_n$
90
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 $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 hy
percube $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$.
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.
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. Hype
rcube-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 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 num
ber 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.
We study Hamiltonicity in random subgraphs of the hypercube $mathcal{Q}^n$. Our first main theorem is an optimal hitting time result. Consider the random process which includes the edges of $mathcal{Q}^n$ according to a uniformly chosen random orderi
ng. Then, with high probability, as soon as the graph produced by this process has minimum degree $2k$, it contains $k$ edge-disjoint Hamilton cycles, for any fixed $kinmathbb{N}$. Secondly, we obtain a perturbation result: if $Hsubseteqmathcal{Q}^n$ satisfies $delta(H)geqalpha n$ with $alpha>0$ fixed and we consider a random binomial subgraph $mathcal{Q}^n_p$ of $mathcal{Q}^n$ with $pin(0,1]$ fixed, then with high probability $Hcupmathcal{Q}^n_p$ contains $k$ edge-disjoint Hamilton cycles, for any fixed $kinmathbb{N}$. In particular, both results resolve a long standing conjecture, posed e.g. by Bollobas, that the threshold probability for Hamiltonicity in the random binomial subgraph of the hypercube equals $1/2$. Our techniques also show that, with high probability, for all fixed $pin(0,1]$ the graph $mathcal{Q}^n_p$ contains an almost spanning cycle. Our methods involve branching processes, the Rodl nibble, and absorption.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
