Ask Your Question

How to generate random graphs free of certain structures?

asked 2014-10-01 08:28:02 -0600

Han gravatar image

updated 2014-10-01 08:55:30 -0600

Is it possible to generate random graphs free of certain forbidden structures? For example, graphs without $C_3$.

Or is it possible to test whether a graph is free of some forbidden structures?

If it is positive, then it would be of great help in my research. Looking forward to all comments and suggestions.

edit retag flag offensive close merge delete



Yes. See, for example, the post "How to list all the connected graphs with 9 vertices?" ( where there is code for generating all graphs on a fixed number of vertices that are connected and long_hole_free. [This page] has some of the properties you can test for. Is_triangle_free would be checking for no $C_3$. Random graphs [here]

dazedANDconfused gravatar imagedazedANDconfused ( 2014-10-01 09:13:43 -0600 )edit

@dazedANDconfused Thank you so much for sharing. I checked the pages you mentioned above, and it is really helpful, especially two functions concerning minors.

Han gravatar imageHan ( 2014-10-02 07:01:17 -0600 )edit

1 answer

Sort by ยป oldest newest most voted

answered 2014-10-01 15:21:15 -0600

tmonteil gravatar image

updated 2014-10-01 17:21:48 -0600

I am pretty sure there is no random generation of graphs forbidding some structure in Sage. So, what is possible is to use a rejection algorithm : pick random graphs of a given size with equal probability until you found one that forbids the given structure. For example, you can do:

sage: def my_random_graph_excluding(C, size):
....:     assert(C.size() <= size), "No chance to find any graph of size {} containing {}".format(n,C)
....:     while True:
....:         G = graphs.RandomGNP(size, 0.5)
....:         if G.subgraph_search(C) is None:
....:              return G

Then you can find a random graph not containing any $C_3$:

sage: G = my_random_graph_excluding(graphs.CycleGraph(3), 7)

Of course this method can take a long time for big size if the set of admissible graphs is small compared to the set of all graphs.

Note that G.subgraph_search(C) searches for a copy of C in G. If you want to avoid only C as an induced subgraph of G, you should replace G.subgraph_search(C) by G.subgraph_search(C, induced=True). Of course it does not matter for the special case where C is $C_3$.

edit flag offensive delete link more


@tmonteil Thank you so much for your suggestions. It is really helpful. The function you mentioned above G.subgraph_search() together with function minor() found by following @dazedANDconfused 's instruction are exactly what I need in my research. Thank you guys for your patient explanations.

Han gravatar imageHan ( 2014-10-02 07:22:01 -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


Asked: 2014-10-01 08:28:02 -0600

Seen: 108 times

Last updated: Oct 01 '14