0

Given a graph $G$ how many labeled graphs are isomorphic to $G$? It seems like it is dependent on the degree sequence of the graph. Is there a term for this function?

xxxxxxxxx
  • 13,302
Eyob Tsegaye
  • 178
  • I don't believe there can be a nice answer to this question. – Benji Altman Dec 19 '17 at 05:07
  • @BenjiAltman Okay, but I just want any sort of information. The name of this function, bounds, anything. – Eyob Tsegaye Dec 19 '17 at 05:10
  • 1
    It is dependent on the degree sequence, but it is not determined by it. Consider for example a sequence $(3,3,3,3,3,3,3,3)$. It could be a degree sequence of the graph with to $K_4$ components or the graph of an octagon with four vertex-independent chords. It's easy to see that the first graph has $\binom{8}{4}$ automorphisms while the second one only has $16$. – Artur Riazanov Dec 19 '17 at 05:15
  • 1
    I don't understand the question. Consider the graph with just one vertex (and no edges). You can label that vertex $A$, or $1$, or "George", or "table", or ..., so you get an uncountable infinity of labeled graphs, and they're all isomorphic. So, what do you really mean? – Gerry Myerson Dec 19 '17 at 05:36
  • @GerryMyerson I'm sorry, I meant automorphic. I edited the question. – Eyob Tsegaye Dec 19 '17 at 05:38
  • I still don't understand. Is $G$ itself a labeled graph? Are you just asking, how many automorphisms does $G$ have? – Gerry Myerson Dec 19 '17 at 05:54
  • @GerryMyerson Yes, that is exactly what I'm asking. – Eyob Tsegaye Dec 19 '17 at 05:55
  • 3
    OK, if that's what you mean to ask, then maybe that's what you should actually ask. Though I think the term is, "number of automorphisms of $G$", and I think it's clear from the comments that you need to know more than the degree sequence. – Gerry Myerson Dec 19 '17 at 06:05
  • See https://math.stackexchange.com/questions/1728708/how-to-determine-all-graph-automorphisms-for-a-given-graph and https://math.stackexchange.com/questions/1381752/number-of-automorphisms-of-a-irregular-graph and https://math.stackexchange.com/questions/1887327/automorphisms-of-a-graph and https://math.stackexchange.com/questions/213716/number-of-automorphisms-of-a-given-graph and https://math.stackexchange.com/questions/229017/working-out-the-number-of-automorphisms-of-a-graph and probably a few more. – Gerry Myerson Dec 19 '17 at 06:21

1 Answers1

2

Determining the automorphism group of a graph is a non-trivial exercise, which is not formulaic in nature (aside from testing all permutations in $\text{Sym}(V(G))$, which is not realistic/feasible).

ml0105
  • 14,674
  • 1
    It may not be formulaic, but it IS possible to determine the automorphism group of a graph. One possibility uses the Schreier-Sims algorithm (https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm) – gilleain Dec 19 '17 at 09:11