2
$\begingroup$

Let's take a graph(undirected) of $m$ edges and $3$ vertices. Now I want to derive a polynomial for which the coefficient of $x^m$ denotes the number of unlabeled graphs of $m$ edges.

How to derive the polynomial in this case? Also is deriving a polynomial means deriving a generating sequence?

$\endgroup$
2
$\begingroup$

Here we require the cycle index of the action on the edges of the symmetric group $S_3$ on the vertices. We find:

  • The identity: $a_1^3.$
  • Three reflections: $3 a_1 a_2.$
  • Two rotations: $2 a_3.$

We get for the cycle index

$$Z(G_3) = \frac{1}{6} ( a_1^3 + 3 a_1 a_2 + 2 a_3 ).$$

Evaluate at $1+z$ for the generating function:

$$Z(G_3; 1+z) = \frac{1}{6} ((1+z)^3 + 3 (1+z) (1+z^2) + 2 (1+ z^3)) \\ = \frac{1}{6} (1+3z+3z^2+z^3 + 3+3z^2+ 3z + 3z^3 + 2+2z^3) = 1 + z + z^2 + z^3.$$

This means there is one graph on three vertices taking into account ismorphisms having zero, one, two and three edges.

The general case is described and implemented at the following MSE link.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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