Let graph $G=(V,E)$ be bipartite graph with partite sets $X = \{x_1, \ldots, x_n\}$ and $Y = \{y_1, \ldots, y_n\}$. Vertices $x_i$ and $y_j$ are connected with edge if and only if $i \neq j$. What would be edge connectivity ($\lambda(G)$) and vertex connectivity($\kappa(G)$) of this graph?

I think that edge connectivity would be $\lambda(G) = 1$ since there are no vertices connected with no more then one edge. But I am not sure, and I don't know vertex connectivity.

Thank you for help

  • $\begingroup$ Are you sure you don't mean that every vertex has precisely $n-1$ neighbours? That would give you $K_{n,n}$ minus one matching. $\endgroup$ – Jernej Apr 13 '15 at 8:39
  • $\begingroup$ @Jernej Yes, I am sure. $\endgroup$ – Superian007 Apr 13 '15 at 8:41
  • $\begingroup$ So in this case your graph is a matching which is a disconnected graph for $n > 1.$ $\endgroup$ – Jernej Apr 13 '15 at 8:42
  • $\begingroup$ What do you mean by "your graph is matching"? And disconnected graph in terms of edge connectivity or vertex connectivity? $\endgroup$ – Superian007 Apr 13 '15 at 9:42
  • $\begingroup$ The graph you describe is the disjoint union of $n$ edges. Hence if $n > 1$ the graph is not connected. But as I said I think you're confused with the definition and in fact want to consider $K_{n,n}$-matching. $\endgroup$ – Jernej Apr 13 '15 at 10:07

Your Answer

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

Browse other questions tagged or ask your own question.