Let $\lambda(G)$ denote the edge-connectivity of $G$.

Consider the following parameter:

$\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$

Has this parameter been studied? Are there any known bounds on it in terms of $\lambda(G)$?

  • 3
    $\begingroup$ can you give some motivation, hove did you came up with this parameter? $\endgroup$ Dec 17 '13 at 2:37
  • $\begingroup$ Looking for ways to identify vulnerability in networks. $\endgroup$
    – hbm
    Dec 17 '13 at 13:28

Note: The question can be rephrased as follows: Two players $A$ and $B$ play a game on a graph. $A$ cuts the graph into two connected components, and $B$ chooses one component of the resulting graph. $A$ wants to maximize and $B$ wants to minimize the edge connectivity of the result. The bounds are the question: What would $A$ or $B$ say if they were to pick the graph.

Upper bound: There is no upper bound in terms of $\lambda(G)$ as you can take two disjoint complete graphs on $k$ vertices and connect them with a single edge. This graph has $\lambda(G)=1$ but you can choose $X$ to be one of the $k$ cliques resulting in $\rho(G)=k-1$.

Lower bound: For the lower bound we couldn't get better examples than $\lfloor \frac{\lambda(G)}{2}\rfloor -1$. This is achieved by $K_{2k+1}$. We could not prove that this is an actual lower bound we only have that: If $\delta(G) >\lambda(G)$ then $\rho(G) > \lfloor \frac{\lambda(G)}{2}\rfloor -1$.

Proof: Consider a cut with $\lambda(G)$ edges which cuts the graph to $G_1$ and $G_2$. Since $\delta(G)> \lambda(G)$ every component contains at least two vertices. Suppose to the contrary that in $G_2$ there is a cut with $\lfloor \frac{\lambda(G)}{2}\rfloor -1$ edges. This cuts $G_2$ to $H_1$ and $H_2$. Now either the cut that cuts $H_1$ from $G$ or the cut that cuts $H_2$ from $G$ has fewer edges than $\lambda(G)$. A contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.