1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

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.