Vulnerability of super extra edge-connected graphs

Chia Wen Cheng, Sun Yuan Hsieh, Ralf Klasing

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


Edge connectivity is a crucial measure of the robustness of a network. Several edge connectivity variants have been proposed for measuring the reliability and fault tolerance of networks under various conditions. Let G be a connected graph, S be a subset of edges in G, and k be a positive integer. If G−S is disconnected and every component has at least k vertices, then S is a k-extra edge-cut of G. The k-extra edge-connectivity, denoted by λk(G), is the minimum cardinality over all k-extra edge-cuts of G. If λk(G) exists and at least one component of G−S contains exactly k vertices for any minimum k-extra edge-cut S, then G is super-λk. Moreover, when G is super-λk, the persistence of G, denoted by ρk(G), is the maximum integer m for which G−F is still super-λk for any set F⊆E(G) with |F|≤m. Previously, bounds of ρk(G) were provided only for k∈{1,2}. This study provides the bounds of ρk(G) for k≥2.

Original languageEnglish
Pages (from-to)1-9
Number of pages9
JournalJournal of Computer and System Sciences
Publication statusPublished - 2020 Mar

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Vulnerability of super extra edge-connected graphs'. Together they form a unique fingerprint.

Cite this