2
$\begingroup$

I'm trying to use the listgraph function in the Combinatorica package:

Needs["Combinatorica`"]
g = ListGraphs[5];
ShowGraph /@ g

However, it only returns all the non-isomorphic graphs. Is it possible to return the isomorphic graphs as well, or at least count the number of isomorphic graphs for each graph?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ take a look at Automorphisms[ ] $\endgroup$ – Dr. belisarius Jul 14 '15 at 17:47
  • 1
    $\begingroup$ Thanks. Yea I guess I could use Length[Automorphisms[ ]] for each element in g to count the degeneracies. $\endgroup$ – Zitao Wang Jul 14 '15 at 17:54
  • $\begingroup$ Is there a way to generate graphs with the vertex labeling fixed? It seems that with ListGraphs the vertices are indistinguishable. For example, if I have v vertices, then there are $v \choose 2$ pairs of vertices, and the total number of graphs generated should be $2^{v \choose 2}$. $\endgroup$ – Zitao Wang Jul 14 '15 at 18:33
  • $\begingroup$ Take a look at mathematica.stackexchange.com/a/60725/193 $\endgroup$ – Dr. belisarius Jul 14 '15 at 18:39
  • $\begingroup$ And mathematica.stackexchange.com/a/85771/193 $\endgroup$ – Dr. belisarius Jul 14 '15 at 18:39
1
$\begingroup$ 
Needs["Combinatorica`"]
g = ListGraphs[5];
Grid[{ShowGraph@#, Length@Automorphisms@#} & /@ g, Frame -> All]

Mathematica graphics

|improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.