On the extraconnectivity of graphs
From MaRDI portal
The authors extend their results on \(n\)-extraconnectivities \(\kappa(n)\) and \(\lambda(n)\) of a connected graph \(G\) with minimum degree \(\delta\), \(n\geq0\) (see [Discrete Math. 125, No. 1-3, 169-176 (1994; Zbl 0796.05058)] and [Discrete Math. 127, No. 1-9, 163-170 (1994; Zbl 0797.05058)]) (only minimum separators \(S\) are considered for which every component of \(G-S\) has more than \(n\) vertices). The authors establish sufficient conditions for \(G\) to attain the upper bound \((n+1)\delta-2n\) for \(\kappa(n)\) and \(\lambda(n)\). For example, if the girth \(g\) of \(G\) is odd and \(n\) is even then \(\lambda(n)\) is optimal whenever the diameter \(D\leq g-1-n\).
Recommendations
Cites work
- Circulants and their connectivities
- Conditional connectivity
- Extraconnectivity of graphs with large girth
- scientific article; zbMATH DE number 4162905 (Why is no real title available?)
- scientific article; zbMATH DE number 4089545 (Why is no real title available?)
- scientific article; zbMATH DE number 3455291 (Why is no real title available?)
- Maximally connected digraphs
- Strongly geodetic graphs
- Sufficient conditions for maximally connected dense graphs
Cited in
(only showing first 100 items - show all)- Sufficient conditions for super \(k\)-restricted edge connectivity in graphs of diameter 2
- Extraconnectivity of hypercubes
- On the existence of edge cuts leaving several large components
- Degree conditions for graphs to be \(\lambda_3\)-optimal and super-\(\lambda _3\)
- On the 3-restricted edge connectivity of permutation graphs
- Extraconnectivity of \(s\)-geodetic digraphs and graphs
- Extraconnectivity of graphs with large girth
- Extraconnectivity of graphs with large minimum degree and girth
- The \(h\)-extra connectivity and \(h\)-extra conditional diagnosability of bubble-sort star graphs
- Structure connectivity of hypercubes
- Conditional connectivity of Cayley graphs generated by transposition trees
- On \(g\)-extra conditional diagnosability of hypercubes and folded hypercubes
- Fault-tolerant strong Menger (edge) connectivity and 3-extra edge-connectivity of balanced hypercubes
- Reliability analysis of twisted cubes
- Structure fault tolerance of hypercubes and folded hypercubes
- Reliability of \((n,k)\)-star network based on \(g\)-extra conditional fault
- Hybrid fault diagnosis capability analysis of regular graphs
- The extra connectivity, extra conditional diagnosability and \(t/k\)-diagnosability of the data center network DCell
- The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model
- Edge fault tolerance of interconnection networks with respect to maximally edge-connectivity
- The \(p\)-restricted edge-connectivity of Kneser graphs
- Vulnerability of super extra edge-connected graphs
- 3-restricted arc connectivity of digraphs
- Structure and substructure connectivity of divide-and-swap cube
- The 3-extra conditional diagnosability of balanced hypercubes under \(\mathrm{MM}^\ast\) model
- Reliability of the round matching composition networks based on \(g\)-extra conditional fault
- The diagnosability of Möbius cubes for the \(g\)-extra condition
- The diagnosability of wheel networks with the condition: 2-extra
- Neighbor connectivity of pancake graphs and burnt pancake graphs
- Reliability analysis of the generalized balanced hypercube
- Structure fault tolerance of WK-recursive networks
- The (strong) structure connectivity and (strong) substructure connectivity of the \(( n , k )\)-bubble-sort network
- On the g-extra diagnosability of enhanced hypercubes
- Neighbor-connectivity of pancake networks and burnt pancake networks
- Reliability evaluation of modified bubble-sort graph networks based on structure fault pattern
- An anti-Ramsey theorem of \(k\)-restricted edge-cuts
- Analysis on component connectivity of bubble-sort star graphs and burnt pancake graphs
- Structure connectivity and substructure connectivity of the crossed cube
- A new proof for exact relationship between extra connectivity and extra diagnosability of regular connected graphs under MM* model
- Structure fault-tolerance of arrangement graphs
- \( R_3\)-connectivity of folded hypercubes
- Reliability and hybrid diagnosis of exchanged hypercube
- Structure connectivity and substructure connectivity of wheel networks
- Reliability measure of multiprocessor system based on enhanced hypercubes
- Conditional diagnosability of multiprocessor systems based on Cayley graphs generated by transpositions
- Super fault-tolerance assessment of locally twisted cubes based on the structure connectivity
- The structure fault tolerance of arrangement graphs
- On g-extra conditional diagnosability of hierarchical cubic networks
- Fault tolerance analysis of hierarchical folded cube
- On the \(g\)-good-neighbor connectivity of graphs
- Structure connectivity and substructure connectivity of bubble-sort star graph networks
- The extra connectivity and extra diagnosability of regular interconnection networks
- Edge fault tolerance of graphs with respect to \(\lambda_{2}\)-optimal property
- The \(h\)-extra connectivity of \(k\)-ary \(n\)-cubes
- Extra diagnosability and good-neighbor diagnosability of \(n\)-dimensional alternating group graph \(AG _n\) under the PMC model
- Bounds on the \(k\)-restricted arc connectivity of some bipartite tournaments
- Structure connectivity and substructure connectivity of twisted hypercubes
- The extra connectivity of the enhanced hypercubes
- Fault tolerance of locally twisted cubes
- The \(g\)-extra connectivity and diagnosability of crossed cubes
- Conditional diagnosability of the \(\mathit{SP}_n\) graphs under the comparison diagnosis model
- Degree conditions for graphs to be maximally k-restricted edge connected and super k-restricted edge connected
- On \(g\)-extra connectivity of hypercube-like networks
- Equal relation between the extra connectivity and pessimistic diagnosability for some regular graphs
- Fault diagnosability of data center networks
- Path and cycle fault tolerance of bubble-sort graph networks
- On extra connectivity and extra edge-connectivity of balanced hypercubes
- 3-extra connectivity of 3-ary \(n\)-cube networks
- Sufficient conditions for restricted-edge-connectivity to be optimal
- A proof of an inequality concerning \(k\)-restricted edge connectivity
- Realizability of fault-tolerant graphs
- Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model
- Disconnecting strongly regular graphs
- Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs
- Edge-disjoint paths in faulty augmented cubes
- Cluster connectivity of hypercube-based networks under the super fault-tolerance condition
- \(h\)-extra \(r\)-component connectivity of interconnection networks with application to hypercubes
- Reliability measure of the \(n\)-th Cartesian product of complete graph \(K_4\) on \(h\)-extra edge-connectivity
- Connectivity for some families of composition networks
- Note on reliability of star graphs
- Structure fault-tolerance of divide-and-swap \(k\)-ary \(n\)-cube
- Extra (component) connectivity and diagnosability of bubble sort networks
- Many-to-many edge-disjoint paths in (n,k)-enhanced hypercube under three link-faulty hypotheses
- The g-extra conditional diagnosability and sequential t/k-diagnosability of hypercubes
- Conditional fault diagnosability of dual-cubes
- Structure connectivity and substructure connectivity of hypercubes
- Toughness of the corona of two graphs
- Sufficient Conditions for Maximally k-Isoperimetric Edge Connectivity of Graphs
- Vertex-transitive graphs that remain connected after failure of a vertex and its neighbors
- Sufficient conditions for a graph to be _k-optimal with given girth and diameter
- Neighborhood conditions for graphs to be super restricted edge connected
- The extra connectivity of bubble-sort star graphs
- Bounds for the super extra edge connectivity of graphs
- \(\{2,3\}\)-extraconnectivities of hypercube-like networks
- Vulnerability of super edge-connected networks
- Edge fault tolerance of graphs with respect to super edge connectivity
- \(k\)-restricted edge-connectivity in triangle-free graphs
- scientific article; zbMATH DE number 1114019 (Why is no real title available?)
- Extraconnectivity of k-ary n-cube networks
- Sufficient conditions for triangle-free graphs to be optimally restricted edge-connected
This page was built for publication: On the extraconnectivity of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923481)
