Restricted connectivity for some interconnection networks
type: Item
instance of: scholarly article
title: Restricted connectivity for some interconnection networks
zbMATH Open document ID: 1325.05100
author: Yingzhi Tian
author: Jixiang Meng
published in: Graphs and Combinatorics
publication date: 2015-09-24T00:00:00Z
review text: This paper studies restricted connectivity and super connectivity of a connected graph \(G\). A vertex-cut \(S\subseteq G\) is called restricted if there is no vertex \(v\in G\), whose neighborhood is contained in \(S\). The restricted connectivity \(\kappa^\prime(G)\) is defined as the order of a minimum restricted vertex-cut in the graph. A vertex-cut is called a super vertex-cut if \(G-S\) contains no isolated vertices. The super connectivity \(\kappa_1(G)\) is defined as the order of a minimum super vertex-cut in \(G\). It is well known that \(\kappa_1(G)\leq\kappa^\prime(G)\). Among other things, the authors prove that \(\kappa_1(K_m\times G_2)=\kappa^\prime(K_m\times G_2)=2k_2+m-2\), where \(G_2\) is a \(k_2 (\geq2)\)-regular and maximally connected graph with girth \(g(G_2)\geq 4\); and \(\kappa_1(G_1\times G_2)=\kappa^\prime(G_1\times G_2)=2(k_1+k_2-1)\), where \(G_i\) is a \(k_i(\geq2)\)-regular and maximally connected graph with girth \(g(G_i)\geq4\) for \(i=1,2\).
reviewed by: Yilun Shang
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C82
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 6484840
zbMATH Keywords: restricted connectivity
zbMATH Keywords: super connectivity
zbMATH Keywords: Cartesian product
zbMATH Keywords: minimal abelian Cayley graph
MaRDI profile type: Publication
full work available at URL: s00373-014-1437-x
OpenAlex ID: W1984370079
cites work: Complexity of network reliability computations
cites work: On unreliability polynomials and graph connectivity in reliable network synthesis
cites work: Synthesis of reliable networks - a survey
cites work: Circulants and their connectivities
cites work: Q5422499
cites work: On computing a conditional edge-connectivity of a graph
cites work: Connectivity of minimal Cayley graphs
cites work: On super connectivity of Cartesian product graphs
cites work: Über den Zusammenhang symmetrischer Graphen
cites work: Minimale \(n\)-fach kantenzusammenhängende Graphen
cites work: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
cites work: Super edge- and point-connectivities of the Cartesian product of regular graphs
cites work: Connectivity of Cartesian products of graphs
cites work: Q4870157
cites work: Q4435203
cites work: Graph theoretic reliability analysis for the Boolean n cube networks
DOI: 10.1007/S00373-014-1437-X
Recommended article: Restricted connectivity for three families of interconnection networks
Recommended article: Q4859015
Recommended article: Connectivity interdiction
Recommended article: iBGP and Constrained Connectivity
Recommended article: Matching preclusion for some interconnection networks
Recommended article: Restricted delivery problems on a network
Recommended article: Q3094520
description: scientific article; zbMATH DE number 6484840