Graphs |

Example:We would like to derive from Theorem a formula for the number of graphs onvvertices. Before we start doing so it should be mentioned thatthis example is the second typical example which we present.The first examples were devoted to the introduction of group theoretical concepts, to the derivation of Sylow's Theorem and to a number theoretic result of Fermat. The only example where a suitable choice ofand_{G}XYwas made in order to define and enumerate a mathematical structure was in fact the composition of two symmetric groups. As this example may have been a little bit artificial we admit that it is only now that we start to apply our paradigmatic actions more systematically. Let us see how suitably chosenG,XandYcan be used in order to define and enumerate the graphs onvvertices.(Later on we shall refine this method by counting these graphs according to the number of edges or according to their automorphism group. Finally we shall even use thisAnsatzin order to construct such graphs and also to generate them uniformly at random.) The way of defining graphs as orbits of groups may at first glance seem to be circumstantial, but we shall see that this definition is very flexible since it can easily be generalized to all other kinds of graphs like multigraphs, directed graphs and so on.

- A
labelled (simple) graphconsists of a set ofverticesand a set ofedgesjoining pairs of vertices, but neitherloops(i.e. edges joining a vertex with itself) nor multiple edges are allowed. Thus a labelled graph onvvertices can be considered (after numbering the vertices from 1 tov, say) as a mapffrom the set[of (unordered) pairs of vertices into the setvchoose 2]Y :=2= {0,1 }, where we putandf( {i,j }):= 1 if an edge joinsiandj,For example, the first one of the two labelled graphs of figure can be identified in this way with the mappingf( {i,j }):= 0 otherwise.f :[defined by4choose 2] -> 2{1,2 } -> 0, {1,3 } -> 0, {1,4 } -> 1, {2,3 } -> 1, {2,4 } -> 0, {3,4 } -> 1.- The symmetric group
Sacts on_{v}and hence also onv[, so that we obtain an action ofvchoose 2]Son_{v}2which is of the form^{ [v choose 2]}as was described in the section of paragigmatic examples. Two labelled graphs are called_{G}(Y^{X})isomorphicif and only if they lie in the same orbit under this action, i.e. if and only if each arises from the other by renumbering the vertices, so that for example the labelled graphs of figure are isomorphic (applyp:=(34) ÎS._{ 4})Two isomorphic labelled graphs with 4 vertices- A
graphGonvvertices is defined to be such an isomorphism class of labelled graphs. It can be visualized by taking any member of the isomorphism class and deleting the labels.This yields for the labelled graphs shown in figure the drawings of figure.The graphs obtained from the labelled ones aboveIt should be clear by now what we mean by a graph, and that in our terminology a graph is

nota pair(V,E)consisting of a setVof vertices and a setEof edges, but that a graphGcan berepresentedby such a pair, so that, for example, the graphs of figure are in factequal.- If we want to allow multiple edges, say up to the multiplicity
k, then we again considerX:= [, but we changevchoose 2]YintoY:= {0, ...,k }=k+1.The elements ofare calledY^{X}=(k+1)^{ [v choose 2]}labelled, while byk-graphsonk-graphsvvertices we mean the orbits ofSon this set._{v}- If we want to allow loops or multiple loops, we replace
Xby the union[, and nowvchoose 2]Èvf(i)=j, fori Î, means that the vertex with the numbervicarries aj-fold loop.- If we want to consider
digraphs(i.e. the edges are directed and neither loops nor parallel edges are allowed), we simply putthe set ofX :=v_{i}^{2}:= {(i,j) Îv^{2}| i not = j },injective pairsover.v

Thus graphs, *k*-graphs, *k*-graphs with loops
and also digraphs can be
considered as symmetry classes of mappings. Several other structures
will later on be obtained in the same way. Having *defined* the graphs
this way we want to *count* them by an application of
Theorem which
means that we have to derive a formula for *c( bar ( p))*, the number of
cyclic factors of * bar ( p)*, the permutation induced by * pÎS _{ v}* on the set

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

Graphs |