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
    Commented Aug 5, 2019 at 6:12
  • $\begingroup$ @M.Winter; not exactly ! I meant minimal independent set $\endgroup$
    – Charlotte
    Commented 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
    Commented 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .