# Is this Graph parameter known?

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)$?

• can you give some motivation, hove did you came up with this parameter? Dec 17 '13 at 2:37
• Looking for ways to identify vulnerability in networks.
– 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.