Thread: Cauchy-Frobenius-Burnside Theorem

Use the Cauchy-Frobenius-Burnside Theorem to determine the number of graphs of order 5. Can someone please assist with this question.

The setup seems like it must be this:

Let

Then G induces an action on the power set of X, . Each subset of X corresponds to some graph with verticies V. Each permutation of the verticies (obviously ) represents a graph isomophism, and visa-versa, so that the orbit under G of a subset A of X (i.e. of a graph) is the set of graphs isomorphic to A.

There's a complication to consider in that and represent the same edge, so we could make them equivalent, and so consider only X/~, and let G act on . That does seem like a sensible way to proceed, as otherwise we'll be wrongly treating and as different graphs, where . I haven't thought it out, but that seems like how it should be handled. Without the equivalence classes, we'd be considering digraphs, not graphs.

That sets it up to apply the CFB Lemma. So the problem becomes computing when . I haven't thought about that, but this maybe will get you started.

Thanks for your response! Can I ask another question, if we let the set of all automorphisms of G under the operation of function composition be the automorphism group of G, which we denote T(G), or simply T. How would you prove:

A graph G has fixing number 1 if and only if G contains an orbit of cardinality |T|. Help with either implication would be great if you can.

I don't recall a definition for "fixing number". I found this online: "The fixing number of a graph G is the smallest cardinality of a set of vertices S such that only the trivial automorphism of G fixes every vertex in S." It makes the statement work, so I'll assume that's the meaning you intend.

For my own benefit, I'm going to reason through what "fixing number" "means", especially for fixing number 1:
1) If S is the set whose cardinality makes the fixing number, then any non-identity automorphism of G moves at least one vertex of S.
2) If fixing number is 1, then S= {v}, so any non-identity automorphism of G moves v.
2') Thus fixing number 1 means there exists v in V(G) such that every non-identity automorphism of g of G satisifies g(v) not= v.
2'') And so fixing number 1 means there exists v in V(G) such that: if g is an automorphism of G, then g(v) = v iff g is the identity.
2''') And so fixing number 1 means there exists v in V(G) such that the stabilizer of x in the automorphism group of G is trivial.
3) Special case: what if G has no non-identity automorphisms? Then every orbit has cardinality 1, and fixing number is 1.

With that in mind, I'll do one direction, and leave the other to you. They're very similar.

Suppose orbit has cardinality .

Let .

Since , must have that images of T's action on v are all distinct.

Thus, since id(v) = v, no other element of T can fix v. Thus S = {v} satisfies the definition for fixing number, and so the fixing number is 1.

That's awesome thanks! For the reverse implication would the following be the idea:

Assume the fixing number is 1, so the fixing set is S = {v} for some vertex v of G. Then the only automorphism that keeps v fixed is id(v) = v and for any other automorphism g we know that g(v) does not equal v. Also if we take any automorphisms g_1 and g_2 from T which are not the identity automorphisms then assume g_1(v) = g_2(v), it follows that g_1g_2(v) = v but since S = {v} satisfies the definition for fixing number it follows that g_1(v) does not equal g_2(v) and the results follows easily from that.

If there is only one automorphism g other that the identity then we still have that g(v) cannot equal v and the results follows.

As you said if G has no non-identity automorphisms then every orbit has cardinality 1, and fixing number is 1.