On restricted connectivities of permutation graphs
On restricted connectivities of permutation graphs
复制标题
DOI：
10.1002/net.20056
复制
发表时间：
2005-05
期刊：
影响因子：
2.1
通讯作者：
C. Balbuena;X. Marcote;P. García-Vázquez
中科院分区：
文献类型：
--
作者：
C. Balbuena;X. Marcote;P. García-Vázquez
取图G的两个不相交的副本，并在两个副本之间加上任意匹配，得到图G的置换图（或广义棱镜）Gπ。排列图可以被看作是一种合适的模型，用于从较小的互连网络构建更大的互连网络，而不会显著增加其最大传输延迟，从而使这些更大的网络具有高度的容错性。对于排列图，本文提供了保证两个连通性参数λ ‘和κ ’的最优值的条件。对于连通图G，限制边连通性λ ' (G)定义为限制边切的最小基数；即，使G−S不连通且S不包含图中任意顶点的关联边集的最小基数S。如果λ ‘ (G) = ξ(G)，则图G是λ ’‐最优的，其中ξ(G)是G中的最小边度，定义为ξ(G) = min{d(u) + d(v)−2:uv∈E(G)}, d(u)表示顶点u的度。此外，我们证明了置换图满足：min{λ ' (G) + δ(G), 2λ ' (G)，如果| v (G) |≥ξ(G) + 2，则ξ(Gπ)}≤λ ' (Gπ)≤ξ(Gπ)。此外,min{2λ(G),ξ(Gπ)}≤λ”(Gπ)≤ξ(Gπ)如果G是三角形还是免费的。我们还研究了考虑受限连通性κ′(G)的顶点情况，并将其与超连通性κ1(G)联系起来；后者被定义为一组顶点（如果有的话）的最小基数，这些顶点的删除会以这样一种方式断开G，即每个剩余的组件至少有两个顶点。例如，我们证明了如果G是无三角形且置换图没有长度为5的循环，则2κ(G)≤κ1(G)≤κ ' (Gπ)≤ξ(Gπ)。©2005 Wiley期刊公司网络，Vol. 45(3), 113-118 2005
A permutation graph (or generalized prism) Gπ of a graph G is obtained by taking two disjoint copies of G and adding an arbitrary matching between the two copies. Permutation graphs can be seen as suitable models for building larger interconnection networks from smaller ones without increasing significantly their maximum transmission delays, in such a way that these larger networks are highly fault‐tolerant. For permutations graphs, in this article we provide conditions that guarantee optimal values for two parameters of connectivity, λ′ and κ′. For a connected graph G the restricted edge‐connectivity λ′(G) is defined as the minimum cardinality of a restricted edge‐cut; that is, the minimum cardinality of a set S of edges such that G − S is not connected and S does not contain the set of incident edges of any vertex of the graph. A graph G is said to be λ′‐optimal if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G defined as ξ(G) = min{d(u) + d(v) − 2 : uv ∈ E(G)}, and d(u) denotes the degree of vertex u. Among other things, we prove that permutation graphs satisfy: min{λ′(G) + δ(G), 2λ′(G), ξ(Gπ)} ≤ λ′(Gπ) ≤ ξ(Gπ) if |V(G) | ≥ ξ(G) + 2. Furthermore, min{ 2λ′(G), ξ(Gπ)} ≤ λ′(Gπ) ≤ ξ(Gπ) if G is triangle‐free. We also study the vertex case considering the restricted connectivity κ′(G) and relating it to the superconnectivity κ1(G); the latter is defined as the minimum cardinality of a set of vertices, if any, whose deletion disconnects G in such a way that every remaining component has at least two vertices. For instance, we prove that 2κ(G) ≤ κ1(G) ≤ κ′(Gπ) ≤ ξ(Gπ) if G is triangle‐free and the permutation graph has no cycles of length five. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 113–118 2005