I'm trying to enumerate the labeled graphs on $n$ vertices having at most $e$ edges. I thought GraphData /@ GraphData[n] and then filtering by edge count would do the trick (albeit slowlt) but this seems to only return some named graphs and it also only has one graph per isomorphism class, which is not what I want.
$\begingroup$
$\endgroup$
1
1 Answer
$\begingroup$
$\endgroup$
2
The idea suggested by @Szabolics in the comment is easily realized by Subsets[ ]:
gen[n_, e_] := Module[{alledges},
alledges = Subsets[Range[n], {2}];
Table[Graph[Range[n], UndirectedEdge @@@ edges,
VertexLabels -> "Name", VertexCoordinates -> CirclePoints[n],
ImageSize -> 50], {edges, Subsets[alledges, e]}]];
gen[5,3]
-
1$\begingroup$ Nice solution, +1! I'll use this approach from now on when I need to generate labelled graphs. You have a small mistake where you wrote
vcinstead ofvcoord. This could be made even simpler by usingVertexCoordinates -> CirclePoints[n]. $\endgroup$– SzabolcsCommented Jul 25 at 10:22 -
$\begingroup$ @Szabolcs Thank you very much :-) Following your comment, I revised my answer. $\endgroup$– A. KatoCommented Jul 25 at 10:31
mmax = Binomial[n,2]fornvertices, and select allm-element subsets ofRange[mmax]. Then create arrays where these positions are set to 1, the rest to 0. Finally use the values in the arrays to fill the upper triangular part of an adjacency matrix.TakeListwill be helpful for partitioning the array,PadLeftfor turning it into a matrix. Finally, symmetrix the matrix and convert to a graph withAdjacencyGraph. I'm sorry, I don't have time to write ready to use code for this. $\endgroup$