1 | initial version |

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)
```

Note that `subgraph_search`

search for a copy of `C`

in `G`

. If you want to avoid only C as an induced subgraph, you should replace `G.subgraph_search(C)`

by `G.subgraph_search(C, induced=True)`

.

2 | No.2 Revision |

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$:`C_3`

:

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

Note that

search G.subgraph_search(C) searches for a copy of ~~subgraph_search~~`C`

in `G`

. If you want to avoid only ~~C ~~`C`

as an induced ~~subgraph, ~~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$.

3 | No.3 Revision |

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

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.