Info on Graphs

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 2^n(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 A000088(M1253) in Neil J. Sloane's database of integer sequences.

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 A001349(M1657) in Neil J. Sloane's database of integer sequences.

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:

Questions?? Email The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 3453 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.