首页>
外文OA文献
>A kind of conditional connectivity of transposition networks generated by $k$-trees
【2h】
A kind of conditional connectivity of transposition networks generated by $k$-trees
展开▼
机译：一种生成的换位网络的条件连通性 按$ k $ -trees
展开▼
免费
页面导航
摘要
著录项
相似文献
相关主题
摘要
For a graph $G = (V, E)$, a subset $Fsubset V(G)$ is called an$R_k$-vertex-cut of $G$ if $G -F$ is disconnected and each vertex $u in V(G)-F$ has at least $k$ neighbors in $G -F$. The $R_k$-vertex-connectivity of $G$,denoted by $kappa^k(G)$, is the cardinality of the minimum $R_k$-vertex-cut of$G$, which is a refined measure for the fault tolerance of network $G$. In thispaper, we study $kappa^2$ for Cayley graphs generated by $k$-trees. Let$Sym(n)$ be the symmetric group on ${1, 2, cdots ,n}$ and $mathcal{T}$ be aset of transpositions of $Sym(n)$. Let $G(mathcal{T})$ be the graph on $n$vertices ${1, 2, . . . ,n}$ such that there is an edge $ij$ in$G(mathcal{T})$ if and only if the transposition $ijin mathcal{T}$. Thegraph $G(mathcal{T})$ is called the transposition generating graph of$mathcal{T}$. We denote by $Cay(Sym(n),mathcal{T})$ the Cayley graphgenerated by $G(mathcal{T})$. The Cayley graph $Cay(Sym(n),mathcal{T})$ isdenoted by $T_kG_n$ if $G(mathcal{T})$ is a $k$-tree. We determine$kappa^2(T_kG_n)$ in this work. The trees are $1$-trees, and the completegraph on $n$ vertices is a $n-1$-tree. Thus, in this sense, this work is ageneralization of the such results on Cayley graphs generated by transpositiongenerating trees and the complete-transposition graphs.
展开▼
机译：对于图$ G =（V，E）$，如果断开$ G -F $并且每个顶点$，则子集$ F 子集V（G）$称为$ G $的$ R_k $ -vertex-cut。 V（G）-F $中的 u在$ G -F $中至少有$ k $个邻居。 $ G $的$ R_k $-顶点连通性由$ kappa ^ k（G）$表示，是$ G $的最小$ R_k $ -vertex-cut的基数，这是对网络$ G $的容错能力。在本文中，我们研究了由$ k $树生成的Cayley图的$ kappa ^ 2 $。设$ Sym（n）$为$ {1，2， cdots，n } $和$ mathcal {T} $上的对称组为$ Sym（n）$的换位集合。令$ G（ mathcal {T}）$为$ n $ vertices $ {1、2 、. 。 。 ，n } $这样，当且仅当转置$ ij in mathcal {T} $时，在$ G（ mathcal {T}）$中存在边ijij $。图$ G（ mathcal {T}）$被称为$ mathcal {T} $的换位生成图。我们用$ Cay（Sym（n）， mathcal {T}）$表示由$ G（ mathcal {T}）$生成的Cayley图。如果$ G（ mathcal {T}）$是$ k $树，则Cayley图$ Cay（Sym（n）， mathcal {T}）$用$ T_kG_n $表示。我们在这项工作中确定$ kappa ^ 2（T_kG_n）$。树是$ 1 $树，$ n $顶点上的completegraph是$ n-1 $树。因此，从这个意义上讲，这项工作是对通过转置生成树和完全转置图生成的Cayley图上的此类结果的概括。
展开▼
