# Vertex connectivity of join of two graphs

Does there exist any results on the vertex connectivity of join of two graphs?

If $$G_1$$ and $$G_2$$ are two graphs what can we say about the vertex connectivity of $$G_1\lor G_2$$ where $$G_1\lor G_2$$ is the join of $$G_1$$ and $$G_2$$? The join of $$G_1$$ and $$G_1$$ is the graph obtained from the disjoint union of $$G_1$$ and $$G_2$$ by adding all edges between $$V(G_1)$$ and $$V(G_2)$$.

If $$\kappa(G)$$ denotes vertex connectivity of a graph $$G$$ how is $$\kappa(G_1\lor G_2)$$ related to $$\kappa(G_1)$$ and $$\kappa(G_2)$$?

• How is the join defined? Commented Feb 9, 2020 at 11:09
• @M.Winter; math.stackexchange.com/a/1769191/665065; check this Commented Feb 9, 2020 at 11:13

The vertex connectivity of $$G_1 \vee G_2$$ is $$\min \{|V(G_1)|+\kappa(G_2), |V(G_2)|+\kappa(G_1)\}$$. To see this, note that if $$X \subseteq V(G_1 \vee G_2)$$ is such that $$V(G_1) \setminus X$$ and $$V(G_2) \setminus X$$ are both non-empty, then $$(G_1 \vee G_2) - X$$ is connected. Thus, a smallest vertex separator $$X$$ of $$G_1 \vee G_2$$ must be of the form $$V(G_1) \cup X_2$$ or $$V(G_2) \cup X_1$$, where $$X_i$$ is a smallest vertex separator of $$G_i$$.