Return to Question

Removed the deprecated (discrete-mathematics) tag - see the tag info: https://mathoverflow.net/tags/discrete-mathematics/info (if there are some other suitable tags, choose some of them instead)

Link

edited Aug 5, 2019 at 5:53

Martin Sleziak

4.7k
4
35
40

Source Link

asked Aug 4, 2019 at 13:07

Charlotte

Relation between vertex connectivity and independent set

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?

graph-theory discrete-mathematics