Suppose there is an undirected, connected graph $G=(V,E)$. Let $U\subseteq V$. Define vertex-deletion subgraph $G−U$ as the graph obtained from $G$ by deleting from $G$ the vertices in $U$ and deleting the edges that directly connected to the vertices in $U$.
For example, in the following graph vertex $5$ and $6$ are deleted and $G$ breaks into $3$ unconnected subgraphs with vertex set $\{1,2,3,4\},\{7\},\{8,9,10,11\}$.
Define the unconnected subgraphs after vertex-deletion as $S_1,S_2,\dots,S_l$.
My question is, given $G$ and the number of vertices in $U$, how to choose $U$ to minimize the degree of the "biggest" subgraph?
$$\text{minimize}\ \max_{i}\{|S_i|\}$$ $$s.t. |U|=n<|V|$$ （We focus on the nontrivial case where $2\leq n\leq \biggl\lceil |G|/2 \biggr\rceil-1$）
In other words, how to choose the "cut vertex" so that the graph is broken down as "small" as possible?
It is clear we can solve this problem by trying all the combinations, but the "forwarding index of G" might be a good hint for how to choose the cut vertex. Is "always choose the vertex that possesses the largest load" the best strategy? Or is there any existing result that could be used to solve this problem?
Some reference:
1 Junming Xu, Topological Structure and Analysis of Interconnection Networks. Springer Science+Business Media, 2001.
(For the term "forwarding index" or "load" please refer to this image)
