GraphEnumeration: A Maple package for Graphical Enumeration

By Doron Zeilberger


Written: July 20, 2010.
This page is a short description of the Maple package GraphEnumeration. It implements the Polya-Redfield method as it is described in Frank Harary and Edgar Palmer clasic masterpiece "Graph Enumeration".

To use it, download it, save it as GraphEnumeration, and type
ezra();
for the list of the main procedures. For help with a specific procedure type: ezra(ProcedureName); For example, with help with procedure Tseq, type:
ezra(Tseq);

The main functions are

  • BnSeq(n): the first n terms of the enumerating sequence for the number of "irreducible" Boolean functions, i.e. the number of equivalence classes of Boolean functions where f(x1, ..., xm) is considered equivalent to g(x1,x2,...,xm) if there exist a permutation π and a subset S of {1, ..., m}, such that permuting the variables under π and then negating the variables in S transforms f to g.

  • BnxSeq(n,x): Like the above but with generating functions according to the number of true rows in the truth table.

  • Cseq(n): The first n terms of the sequence enumerating unlabeled connected graphs.

  • Cseqx(n,x): like the above, but with generating functions according to the number of edges.

  • HGseq(k,n): the first n terms in the enumerating sequence for unlabeled regular k-hyper-graphs

  • HGseqx(k,n,x): as above, but generating functions according to "edges"

  • Gseq(n): the first n terms in the enumerating sequence for unlabeled graphs (same as HGseq(2,n) )

  • Gseqx: as above, but generating functions according to edges

  • RTseq(n): the first n terms in the enumerating sequence for unlabeled rooted trees (following Cayley)

  • Tseq(n):the first n terms in the enumerating sequence for unlabeled trees (following Cayley)

    [Note: this is the default sequence in Sloane (viewed July 20, 2010)]

  • UGdeg(L): the number of all (connected or not) unlabeled (simple) graphs with degree sequence L

  • UMGdeg(L): the number of all (connected or not) unlabeled multi-graphs with degree sequence L


Sample Input and Output for GraphEnumeration

  • To see the first 10 terms of the sequence enumerating equivalence classes of Boolean functions under permutation of variables and negation
    the input gives the output.

    [Note: this is Sloane's A000616, first computed by M.A. Harrison; we computed two extra terms].

  • To see the first 7 terms of the the sequence of weight-enumerators enumerating equivalence classes of Boolean functions under permutation of variable and negation the
    input gives the output.

  • To see the first 20 terms of the sequence enumerating connected unlabeled graphs the
    input gives the output.

    [Note: this is Sloane'sA001349]

  • To see the first 20 terms of the sequence enumerating unlabeled graphs the input gives the output.

    [Note: this is Sloane'sA000088]

  • To see the first 60 terms of the sequence enumerating unlabeled trees, the
    input gives the output.

    [Note: this is Sloane'sA000055, apparently Neil's favorite sequence, since this is the sequence that you get as "default"]

  • To see the first 20 terms of the sequence enumerating regular 3-hypergraphs
    the input gives the output.

    [Note: this is Sloane'sA000665, except that he only gives 11 terms.]

  • To get the number of unlabeled simple graphs with 6 vertices where each vertex has degree 3 equals
    the input gives the output.

  • To get the number of unlabeled multigraphsgraphs with 6 vertices where each vertex has degree 3 equals
    the input gives the output.


Doron Zeilberger's Maple Programs

Doron Zeilberger's Home Page