## 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.

[Error Opening Counter File -- Click for more info]

©Frank Ruskey, 1995-2003.