Message Boards Message Boards

GROUPS:

Generate all subgraphs of a undirected graph?

Posted 1 year ago
1169 Views
|
1 Reply
|
3 Total Likes
|

Given an undirected graph G, is it possible to generate a list of all subgraphs of G which have a fixed number of edges with Mathematica?

Is having a fixed number of edges the only criterion, or do you also need them to be connected graphs?

If you only want the subgraphs with a given number of edges, regardless of whether they are connected, you can use Subsets

SeedRandom[42];
g = RandomGraph[{8, 12}];

edgelists = Subsets[EdgeList[g],{5}];

subgraphs = Subgraph[g, #] & /@ edgelists;

Length@edgelists
(* 792 *)
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract