Information on (Unlabelled) Graphs

Not much here yet. Will eventually include an elementary discussion of the difference between labelled and unlabelled graphs along with some illustrations, and perhaps something about orderly algorithms.

A labelled graph G = (V,E) consists of a finite set of vertices V together with a set E of 2-subsets of V. The elements of E are called edges. The number of labelled graphs whose vertex set is [n] = {1,2,...,n} is 2n(n-1)/2. Two graphs G and H, both with vertex set [n], are said to be isomorphic if there is a permutation p of [n] such that {u,v} is in E(G) if and only if {p(u),p(v)} is in E(H). Isomorphism induces an equivalence relation on the set of all labelled graphs and the equivalence classes of this relation are the unlabelled graphs.

The number of n vertex unlabelled graphs for n = 1,2,...,12, is 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592. This is sequence Anum=A000088"> A000088(M1253) in

The number of n vertex unlabelled connected graphs for n = 1,2,...,12, is 1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476. This is sequence Anum=A001349"> A001349(M1657) in

The programs used are Brendan McKay's makeg and makebg (for bicoloured graphs), both of which uses his nauty program. The latest versions of all these programs may be obtained thru his home page.


Programs available:


It was last updated .