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?

$\endgroup$
  • $\begingroup$ When you say "independent set", do you mean "maximal independent set"? $\endgroup$ – M. Winter Aug 5 '19 at 6:12
  • $\begingroup$ @M.Winter; not exactly ! I meant minimal independent set $\endgroup$ – Math_Freak Aug 5 '19 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 '19 at 8:00
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


| cite | improve this answer | |
$\endgroup$

Your Answer

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

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