Ask Your Question
0

Code to find separating set in SageMath of a given Graph

asked 2019-08-04 07:52:38 -0600

Captcha gravatar image

Given a Graph $G$ how can I find the separating set of the Graph?

Suppose I am given this graph G=Graph({1:[2,3,4,5],2:[1,3,4,5],3:[1,2,4,5],4:[1,2,3],5:[1,2,3]})

I want to find the set of vertices whose removal disconnects the graph.

I found that the vertex connectivity of $G$ is 2.

Also on seeing the graph I find that the set of vertices whose removal disconnects the graph will be $(1,2,3)$

But how to find it using a code in SageMath?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2019-08-04 10:27:23 -0600

dazedANDconfused gravatar image

Try this code:

from sage.graphs.connectivity import vertex_connectivity
G=Graph({1:[2,3,4,5],2:[1,3,4,5],3:[1,2,4,5],4:[1,2,3],5:[1,2,3]})
vertex_connectivity(G,value_only=False)

The result, running in a SageCell Server is

(3, [1, 2, 3])

Which says the vertex connectivity is 3 and the vertices 1,2,3 are such a set.

The documentation for vertex_connectivity() is here.

edit flag offensive delete link more

Comments

Thanks a lot sir. Can you kindly tell if there is any code which can find all the minimal separating sets of a given graph? How to write such a code

Captcha gravatar imageCaptcha ( 2019-08-05 00:53:28 -0600 )edit

I don't see anything in the documentation that would provide all minimal separating sets of a graph. Given that circulants would have a lot of vertex separating sets, I don't see any way around brute force checking whether the removal of k vertices (where k is the vertex connectivity) over all subsets of k vertices results in a disconnected graph. If so add to the list.

dazedANDconfused gravatar imagedazedANDconfused ( 2019-08-05 09:52:55 -0600 )edit

Okay Thank you so much

Captcha gravatar imageCaptcha ( 2019-08-05 20:53:23 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2019-08-04 07:52:38 -0600

Seen: 152 times

Last updated: Aug 04