perm filename ENUMER.DOC[DOC,LMM] blob sn#044082 filedate 1973-05-18 generic text, type T, neo UTF8

                           Larry Masinter
                         Stanford University
                     Computer Science Department

      ABTRACT. Previously,  enumerations   of  the   number  of
      equialence classes of graphs with a given partitions have
      been  given (1,2).  These  results are  extended  to give
      enumerations  for the  number of  equivalence  classes of
      connected multigraphs.  Connected  multigraphs correspond
      directly  with chemical  molecules; thus  the enumeration
      can be  applied to count  the number of  chemical isomers
      constructable from a given  set of atoms.  Bounds  may be
      placed on the multiplicity of each edge,  corrsponding to
      restructions on multiple bonds in chemical structures.

               ENUMERATION OF THE GRAPHS OF MOLECULES               1



Def.  A  multi-graph of order  n is the  set N={1,...,n}  (called the         ___________
nodes  of  the  graph)  together  with  a  mapping  f  from  the  set_____
E(n)={{i,j}|1≤i<j≤n} to the  set of non-negative integers  I+.  Those
eεE  for  which  f(e)≠0  are  said to  be  edges  of  the  graph; the
multiplicity of e is f(e).  Also,  if e={i,j} then node i is  said to____________
be connected to node j with multiplicity f({i,j}).   Multi-graphs may
be restricted  to those  whose edges have  maximum multiplicity  k by
restricting the range of f  to be the set of integers  {0,1,...,k}. A
k-multigraph is thus an element of k    .____________

Def. The degree  of a node nεN  is d(n)=∃   f({n,m}).  The  degree is         ______
the  total  number  of  other nodes  n  is  connected  to,  with each
connection counted the appropriate multiplicity number of times.

Def. The degree  seqence of a  graph f is  defined to be  the ordered         ______  _______
list       ds(f)=(o ,o ,...),      where       o ≤o ≤...≤o ,      and
                   1  2                         1  2      n
|{j:o =k}|=|{l:d(l)=k}|. It is the sorted list of the degrees  of the
nodes of f.

Def. Given a set X, the symmetric group on X, or S , is defined to be                        _________ _____ __ _
the set of all automorphisms from X onto X.

Def. Two graphs f,  g of order n are  said to be isomorphic  if there                                                 __________
exists a permutation  αεS  such that  ∀i,jεN f({i,j})=g({α(i),α(j)}).
This is written f↔g.

Lemma.  f↔g => ds(f) = ds(g).

Def.  Given a set F and an equivalence relation ↔ on F, we define the
set of  equivalence classes  of F under  ↔, F/↔,  to be  {{fεF:f↔g} |

               ENUMERATION OF THE GRAPHS OF MOLECULES               2


Thus, the the problem is to find a generating function for the number
of equivalence classes of k-multigraphs with a given  degree sequence
(o ,o ,o ,...)
  0  1  2

Burnside lemma.

Given a set E,  and a group G, a  mapping %:G→S , a set B,  and #=B ;
and the equivalence relation for f,gε#  f↔g if there exists  αεG such
that f=g⊗%(α).

Given a weight function w:#→@, where  @ is a field, such that  f↔g =>

For F an  equivalence class in  #/↔, define W(F)  to be w(f)  for any
fεF.  Then
  ∃  W(F) = -  - ∃    ∃   w(f).
Fε#/↔       |G| αεG f=f⊗%α

To  apply the  Bernside lemma  to this  problem, it  is  necessary to
devise a weight  function such that two  graphs with the  same degree
sequence  have  the  same weight  and  graphs  with  different degree
sequences have different weights. Further, to construct  a generating
function for the  number of graphs  with given degree  sequences, the
degree sequences should be reflected in the exponents of terms in the
weight rather than in the coefficient.

Thus, we define the weight function w  on k     into the set  of real
polynomials in u ,u ,...,u  by:
                1  2      n
        w (f)=   π    (u u )
         o    1≤i<j≤n   i j

               ENUMERATION OF THE GRAPHS OF MOLECULES               3

The exponent of u  in w (f) will be the degree of node i in the graph
                 i     o
(N,f).   Unfortunately, ds(f)=ds(g)  (or  even f↔g)   does  not imply
w (f)=w (g);  although f  and g  have the  same degree  sequence, the
 o     o
exponents may be permuted among  the u .  It is necessary to  apply a
symmetrizing operator ∂:

Def. For w a function in u , u , ... u , define
                          1   2       n
∂(w)(u ,u ,...,u )=--   ∃  w(u  ,u  ,...,u  )
      1  2      n  n! αεS     α   α       α
                         N     1   2       n

Note:   1) ∂ is linear
        2) if w is symmetric, then ∂w=w;
           specifically, ∂∂w=∂w for any w.

The weight function w can now be defined by:
        for fεk ,  w(f)=∂w (f).

This  weight  function  satisfies  our  requirements:  if  the degree
sequence of f is o ≤o ≤o ≤...o , the weight of f will be:
                  1  2  3     n

                  o1 o2    on
                ∂u  u  ...u
                  1  2     n

Then,   using  the   definition  of   ↔  given   earlier,   with  the
representation of the group G=S  by:

Def. %:S →S  by %(β){i,j}={β(i),β(j)}
        N  E

we obtain:

               ENUMERATION OF THE GRAPHS OF MOLECULES               4

  ∃  w(f)=--   ∃    ∃  w(f)
fε#/↔     n! αεS  f=f⊗%α
        =-- ∂  ∃    ∃    w (f)
         n!  αεS  f=f⊗%α  o

Consider   ∃  w (f) and the  cycles of %α.  f=f⊗%α <=> f  is constant
on each cycle of %α.  For a  given α, let M  be the number  of cycles
of %α; for 1≤r≤M , let C  be the set of edges (elements of E)  in the
                α       r
r-th cycle of %α, and
U =   π    u u
 r {l,p}εC  l p

Then for f=f⊗%α,

w (f)= π (u u )
 o    i,j  i j

       M    α f(cycle r)
     = π  (U )
      r=1   r

Since each f=f⊗%α can be specified by its value on the cycles  of %α,
there  is a  1-1 correspondence  between such  f  and ∨ε{0,1,...,k} ,
where k is the maximum  multiplicity (can be ∞), by  ∨(r)=f(cycle r).
In particular,
                          Mα    α  ∨(r)
  V(α)   =  ∃   w (f) =∃  π  ( U  )
          f=f⊗%α o     ∨ r=1    r

               ENUMERATION OF THE GRAPHS OF MOLECULES               5

            Mα 1-(U )        Mα   1  
         =  π      r         π  ------- if k=∞)               ------- (or }
           r=1 1 - U        r=1 1-U
                    r              r

Our generating function is now  --∂  ∃   V(α).  We wish to  group the
                               n!  αεS
summation by those permutations α with cycle  index  λ +2λ +...+nλ =n
                                                      1   2       n
(λ  is the number of i-cycles of α; note that this is  different from
the number  of various  cycles of %α).   Let α (λ ,λ ,...,λ )  be the
                                                 1  2      n
permutation  obtained by  filling in  the integers  1,...,n  into the
slots in
  (.)(.)...(.) (..)(..)(..) ... (.. ...)
   ----------   ----------       -----
   λ  1-cycles  λ  2-cycles ... λ  n-cycles
    1            2               n

             ⊗ -1                                  ⊗
For ∨εS ,  ∨α ∨   has the same cycle structure as α ;  further, there
                             n     k
are exactly Y(λ ,λ ,...,λ )= π  (k  λ !) such permutations.
               1  2      n  k=1      k


                          1             ⊗ -1
  ∃   V(α) =     ∃      -----   ∃   V(∨α ∨  )
αεS         λ +...+λ =n Y(λ)  ∨εS       λ
   N         1      n            N