Ask Your Question

# How to generate random graphs free of certain structures?

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 close merge delete

## Comments

1

Yes. See, for example, the post "How to list all the connected graphs with 9 vertices?" (http://ask.sagemath.org/question/24299/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] http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html has some of the properties you can test for. Is_triangle_free would be checking for no $C_3$. Random graphs [here] http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.html

( 2014-10-01 16:13:43 +0200 )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.

( 2014-10-02 14:01:17 +0200 )edit

## 1 Answer

Sort by ยป oldest newest most voted

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$.

more

## Comments

@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.

( 2014-10-02 14:22:01 +0200 )edit

## Your Answer

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

Add Answer

## Stats

Asked: 2014-10-01 15:28:02 +0200

Seen: 565 times

Last updated: Oct 02 '14