edge connectivity

• 2022/09 Tran2022
  • page 19 : bounded twin-cover number does not imply bounded edge connectivity – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
  • page 19 : bounded edge connectivity does not imply bounded twin-cover number – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
• https://mathworld.wolfram.com/EdgeConnectivity.html
  • edge connectivity – The edge connectivity, also called the line connectivity, of a graph is the minimum number of edges $\lambda(G)$ whose deletion from a graph $G$ disconnects $G$.
• unknown
  • minimum degree $k$ upper bounds edge connectivity by $\mathcal O(k)$ – Removing edges incident to the minimum degree vertex disconnects the graph.
  • bisection bandwidth $k$ upper bounds edge connectivity by $\mathcal O(k)$ – By definition
  • graph class complete has unbounded edge connectivity – Parameter is unbounded for the graph class of cliques.
  • graph class bipartite has unbounded edge connectivity