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$.
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
@dazedANDconfused Thank you so much for sharing. I checked the pages you mentioned above, and it is really helpful, especially two functions concerning minors.