3
$\begingroup$

What is the relationship between vertex connectivity and independent set of a connected graph?

Suppose we have a graph on $20$ vertices which is connected.

If the independent set has cardinality $3$ what can we conclude about the vertex connectivity of the graph?

Another question :

Is there any algorithm to find the separating set of a graph?

Given a graph $G$ does there exist any command in SageMath or in any other software which can say the minimum separating set of a graph?

Improve this question
$\endgroup$
3
  • $\begingroup$ When you say "independent set", do you mean "maximal independent set"? $\endgroup$
    – M. Winter
    Aug 5, 2019 at 6:12
  • $\begingroup$ @M.Winter; not exactly ! I meant minimal independent set $\endgroup$
    – Charlotte
    Aug 5, 2019 at 13:59
  • $\begingroup$ Ok, it seems you do not mean "cardinality-wise minimal independent set", as this would be the empty set, which is independent and certainly minimal in size. What do you mean then? $\endgroup$
    – M. Winter
    Aug 8, 2019 at 8:00

1 Answer 1

Reset to default
2
$\begingroup$

Addressing just this:

"Given a graph 𝐺 does there exist any command in SageMath or in any other software which can say the minimum separating set of a graph?"

This set is known as a minimum vertex cut.

For the icosahedral graph $G$ below, Mathematica's FindVertexCut[G] yields {3, 5, 6, 9, 10}, which surround and isolate vertex $1$.

          IcosaG

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.