Sufficient conditions for super \(k\)-restricted edge connectivity in graphs of diameter 2
type: Item
instance of: scholarly article
title: Sufficient conditions for super \(k\)-restricted edge connectivity in graphs of diameter 2
zbMATH Open document ID: 1162.05029
published in: Discrete Mathematics
publication date: 2009-04-09T00:00:00Z
review text: For a connected graph \(G=(V,E)\), a subset \(S\subseteq E\) is a \(k\)-restricted edge cut if \(G-S\) is disconnected and every component of \(G-S\) has at least \(k\) vertices. The \(k\)-restricted edge connectivity of \(G\), denoted by \(\lambda_k(G)\), is defined as the cardinality of a minimum \(k\)-restricted edge cut. Let \(\xi_k(G)=\min\{|[X,\overline X]|: |X|=k, G[X]\text{ is connected}\}\). \(G\) is \(\lambda_k\)-optimal if \(\lambda_k(G) = \xi_k(G)\). Moreover, \(G\) is super-\(\lambda_k\) if every minimum \(k\)-restricted edge cut of \(G\) isolates one connected subgraph of order \(k\). In this paper, the authors prove that if \(|N_G(u)\cap N_G(v)| \geq 2k-1\) for all pairs \(u,v\) of nonadjacent vertices, then \(G\) is \(\lambda_k\)-optimal; and if \(|N_G(u)\cap N_G(v)| \geq 2k\) for all pairs \(u, v\) of nonadjacent vertices, then \(G\) is either super-\(\lambda_k\) or in a special class of graphs.
reviewed by: Jun-Ming Xu
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5542385
zbMATH Keywords: connectivity
zbMATH Keywords: edge-connectivity
zbMATH Keywords: restricted edge-connectivity
zbMATH Keywords: optimality
zbMATH Keywords: diameter
author: Shiying Wang
author: Shangwei Lin
author: Chunfang Li
MaRDI profile type: Publication
full work available at URL: j.disc.2008.01.037
OpenAlex ID: W2121067592
cites work: Superconnectivity of bipartite digraphs and graphs
cites work: On restricted connectivities of permutation graphs
cites work: Sufficient conditions for λ′‐optimality in graphs with girth g
cites work: Q5422499
cites work: Edge-cuts leaving components of order at least three
cites work: On computing a conditional edge-connectivity of a graph
cites work: On the extraconnectivity of graphs
cites work: On Isoperimetric Connectivity in Vertex-Transitive Graphs
cites work: Sufficient conditions for \(\lambda'\)-optimality in graphs of diameter 2
cites work: Sufficient conditions for graphs to be ??-optimal, super-edge-connected, and maximally edge-connected
cites work: Results on the edge-connectivity of graphs
cites work: Q4260012
cites work: Optimally super-edge-connected transitive graphs
cites work: On a kind of restricted edge connectivity of graphs
cites work: Edge cuts leaving components of order at least \(m\)
cites work: Q4079637
cites work: Sufficient conditions for maximally connected dense graphs
cites work: Conditional edge connectivity properties, reliability comparisons and transitivity of graphs
cites work: On restricted edge-connectivity of graphs.
cites work: A proof of an inequality concerning \(k\)-restricted edge connectivity
cites work: Degree conditions for restricted-edge-connectivity and isoperimetric-edge-connectivity to be optimal
DOI: 10.1016/J.DISC.2008.01.037
description: scientific article; zbMATH DE number 5542385