On computing a conditional edge-connectivity of a graph
From MaRDI portal
The conditional edge-connectivity \(\lambda\) (G:P) of a graph G(V,E) has been defined by Harary as the minimum cardinality \(| S|\) of a set S of edges such that G-S is disconnected and every component of G-S has the given graph property P. In this article we present lower and upper bounds for \(\lambda\) (G:P) when P is defined as follows: A graph H satisfies property P if it contains more than one vertex. We then present a polynomial-time algorithm for the computation of \(\lambda\) (G:P). A new generalization of the notion of connectivity is also given.
Recommendations
- On conditional edge-connectivity of graphs
- Conditional edge connectivity properties, reliability comparisons and transitivity of graphs
- On the generalized (edge-)connectivity of graphs
- On the edge-connectivity vector of a graph
- scientific article; zbMATH DE number 961975
- On computing the connectivities of graphs and digraphs
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- On computing of a conditional edge connectivity of alternating group network
- Edge-connectivities of graphs and digraphs
- On the conditional edge connectivity of double-orbit graphs
Cites work
Cited in
(only showing first 100 items - show all)- On super edge-connectivity of product graphs
- Diameter-sufficient conditions for a graph to be super-restricted connected
- On 3-restricted edge connectivity of undirected binary Kautz graphs
- Sufficient conditions for super \(k\)-restricted edge connectivity in graphs of diameter 2
- On the existence of edge cuts leaving several large components
- Degree conditions for graphs to be \(\lambda_3\)-optimal and super-\(\lambda _3\)
- Calculating the extremal number \(ex(v;\{C_3,C_4,\dots,C_n\})\)
- On the 3-restricted edge connectivity of permutation graphs
- Minimally 3-restricted edge connected graphs
- 3-restricted connectivity of graphs with given girth
- Super connectivity of line graphs
- Sufficient conditions for \(\lambda ^{\prime}\)-optimality of graphs with small conditional diameter
- Sufficient conditions for bipartite graphs to be super-\(k\)-restricted edge connected
- Edges of degree \(k\) in minimally restricted \(k\)-edge connected graphs
- The k-restricted edge connectivity of undirected Kautz graphs
- The super connectivity of shuffle-cubes
- On a kind of restricted edge connectivity of graphs
- Bound on m-restricted edge connectivity
- On conditional edge-connectivity of graphs
- The \(h\)-extra connectivity and \(h\)-extra conditional diagnosability of bubble-sort star graphs
- The super connectivity of folded crossed cubes
- Arc fault tolerance of Cartesian product of regular digraphs on super-restricted arc-connectivity
- Structure connectivity of hypercubes
- On restricted edge-connectivity of replacement product graphs
- Sufficient conditions for graphs with girth \(g\) to be maximally \(k\)-restricted edge connected
- Every 3-connected essentially 10-connected line graph is Hamilton-connected
- Super restricted edge-connectivity of vertex-transitive graphs
- Super edge-connectivity of de Bruijn and Kautz undirected graphs
- Cuts leaving components of given minimum order
- Some results on \(R_2\)-edge-connectivity of even regular graphs
- Sufficient conditions for '-optimality in graphs of diameter 2
- On the construction of most reliable networks
- Restricted fault diameter of hypercube networks
- On super restricted edge connectivity of half vertex transitive graphs
- The super connectivity of exchanged hypercubes
- Codes from incidence matrices of graphs
- On bondage numbers of graphs: a survey with some comments
- Structure and substructure connectivity of balanced hypercubes
- Connectivity and super connectivity of the divide-and-swap cube
- Vulnerability of super extra edge-connected graphs
- Some results about the reliability of folded hypercubes
- Structure and substructure connectivity of divide-and-swap cube
- Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs
- Neighbor connectivity of pancake graphs and burnt pancake graphs
- On conditional connectivity of the Cartesian product of cycles
- Structure fault tolerance of balanced hypercubes
- Edge fault-tolerance analysis of maximally edge-connected graphs and super edge-connected graphs
- The \(h\)-restricted connectivity of the generalized hypercubes
- On the edge-connectivity of graphs with two orbits of the same size
- On the \(g\)-good-neighbor connectivity of graphs
- On the sizes of bi-k-maximal graphs
- Edge fault tolerance of graphs with respect to \(\lambda_{2}\)-optimal property
- Degree conditions for graphs to be maximally k-restricted edge connected and super k-restricted edge connected
- Arc fault tolerance of Kautz digraphs
- On \(g\)-extra connectivity of hypercube-like networks
- A sufficient condition for graphs to be super \(k\)-restricted edge connected
- Edge fault tolerance analysis of a class of interconnection networks
- Fault-tolerant analysis of a class of networks
- Restricted arc-connectivity of digraphs
- A bound on 4-restricted edge connectivity of graphs
- Note on the connectivity of line graphs
- Super cyclically edge-connected vertex-transitive graphs of girth at least 5
- Super-cyclically edge-connected regular graphs
- \(\lambda ^{\prime}\)-optimally connected mixed Cayley graphs
- The minimum restricted edge-connected graph and the minimum size of graphs with a given edge-degree
- Generalized measures of fault tolerance in exchanged hypercubes
- Restricted arc-connectivity in tournaments
- Restricted arc-connectivity of bipartite tournaments
- A sufficient condition for graphs to be \(\lambda_k\)-optimal
- Sufficient conditions for restricted-edge-connectivity to be optimal
- On the edge-connectivity and restricted edge-connectivity of a product of graphs
- Fault-free Hamiltonian cycles in crossed cubes with conditional link faults
- On optimally-\(\lambda^{(3)}\) transitive graphs
- Super restricted edge connectivity of regular graphs
- A proof of an inequality concerning \(k\)-restricted edge connectivity
- Edge cuts leaving components of order at least \(m\)
- On edge cut of graphs leaving components of order at least five
- A new approach to finding the extra connectivity of graphs
- Structure and substructure connectivity of alternating group graphs
- Edge fault-tolerance of strongly Menger edge connected graphs
- Reliability measure of the \(n\)-th Cartesian product of complete graph \(K_4\) on \(h\)-extra edge-connectivity
- Connectivity and super connectivity of the exchanged 3-ary \(n\)-cube
- Structure fault-tolerance of divide-and-swap \(k\)-ary \(n\)-cube
- Many-to-many edge-disjoint paths in (n,k)-enhanced hypercube under three link-faulty hypotheses
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- Structure connectivity and substructure connectivity of hypercubes
- On m-restricted edge connectivity of undirected generalized De Bruijn graphs
- On restricted edge-connectivity of lexicographic product graphs
- On restricted edge-connectivity of vertex-transitive multigraphs
- Robustness of random graphs based on graph spectra
- Sufficient conditions for k-restricted edge connected graphs
- A survey of some network reliability analysis and synthesis results
- Sufficient conditions for a graph to be _k-optimal with given girth and diameter
- Neighborhood conditions for graphs to be super restricted edge connected
- Robustness of regular ring lattices based on natural connectivity
- Restricted connectivity of total digraph
- Bounds for the super extra edge connectivity of graphs
- Upper bounds for domination related parameters in graphs on surfaces
- Conditional graph connectivity relative to hereditary properties
- The maximal restricted edge connectivity of Kautz undirected graphs
This page was built for publication: On computing a conditional edge-connectivity of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095928)
