If I have a connected graph $G$, is it true that subgraphs(corresponding to cuts) having minimum conductance or expansion(or other connectivity measures) should be connected? In other words if $S$ is a subgraph for which $\phi(G) = |\delta(S)|/|S| $ does this imply that $S$ and $V-S$ are connected?

NOTE: Assuming $S$ having at least two connected components (and $S_1$ one of them) I tried to use the connectedness of the graph to make cut $S' = S - S_1$ reduce the nominator of the fraction and controlling min(|S'|,|V_S'|) but it seems that this does't work!

  • 1
    $\begingroup$ The answer is no. For example consider the star graphs. $\endgroup$ – Mahdi Jan 6 at 8:59

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.