NASA CR

STAR

Interim Report to the
National Aeronautics and Space Administration
Grant    NsG 81-60

L-
                      DENDRAL-64

A SYSTEM FOR COMPUTER CONSTRUCTION, ENUMERATION AND NOTATION OF

ORGANIC MOLECULES AS TREE STRUCTURES AND CYCLIC GRAPHS
                                                                   1

I-                           -__--., --._ -_.

Part II.  Topology of Cyclic Graphs
- ~__        I
                                 -

Introduction

   Part I showed the canonical formulation of those chemical graphs which

are pure trees.  In Part II we introduce the formulation of pure rings, i.e.

strictly cyclic graphs, each defined as a set of atoms not separable by less

than two cuts.  Part III will relate this topological analysis to the repre-

sentation of complete structures.  These are trees on which each ring will be

regarded as a special node.

submitted by

Joshua Lederberg
Professor of Genetics
School of Medicine
Stanford University
Palo Alto, California

Studies related to this report have been supported by research
grants from the National Aeronautics and Space Administration (NsG 81-60),
National Science Foundation (NSF G-6411), and National Institutes
of Health (NG-04270, AI-5160 and FR-00151).

PART II.  December 15. 1965


PART II.  TABLE OF CONTENTS

2.0

2.1


2.2


2.3

2.4


2.5

2.6


2.7

2.8


2.9

2.T

Introduction to the Treatment of Cyclic Compounds in
Organic Chemistry.

General Introduction to the Treatment of Rings.

The Trivalent Cyclic Graphs.

Numbering of Vertices and Edges.

Quadrivalent Vertices.

Planar Mesh Representations.

Further Developments in the Theory of Trivalent Graphs.

Symmetry Classification;  General Systematics of Graphs.

Coding and Reconstruction of a Hamilton Circuit.

Algorithm for Finding Hamilton Circuits of a Cyclic
Graph.

Tables.


   This part consists mainly of an analysis of cyclic graphs to allow the    2, r;c

enumeration of the ring structures of chemistry.  Many chemical graphs are

mixed, that is are trees in which cyclic subgraphs are embedded.  The complete

representation of such structures is taken up in Part III, and we will be con-

cerned here only with the fundamentals of pure cyclic graphs.

   The most frequent ring in organic chemistry is the simple cycle, e.g.,    Z.Q/

benzene; and these structures (ring structures with one ring) afford no special

problems as they are simple mappings of a linear chain. A canonical form would

be the cut which maximizes the DENDRAL value of the string. The encoding of

the following figures is self evident:

0    P-h
       i.e., I   I
     X/c

C-6)

   N
0

(-N.5)

  S
i'
     N

(-S.C.N.2)

Polycyclic structures such as

STEROID NUCLEUS      MORPHINE NUCLEUS

NAPHTHALENE

BIPHENYL

[41             [51           r21         r11, [II

are, however , quite important and require a more elaborate treatment.  The

chemist refers to a ring-structure (or "ring", when the context makes this

clear) for a set of atoms inseparable by a single cut.  The number of rings

(bracketed above) in such a structure is the minimum number of cuts needed to


convert the structure to a tree.  For a polyhedron (a planar graph everywhere

at least 3-connected), this is one less than the number of faces, i.e., the

number of cuts needed to separate the graph, a definition we can generalize

to 2-connected graphs as well.

General Introduction to the Treatment of Rings.

Attempts to process rings on a node-by-node basis like linear DENDRAL    g;z,/o

proved unrewarding.  Ambiguities due to symmetry are usual, and many paths

can be evaluated only by recursively searching through the entire graph.  This

approach was therefore abandoned in favor of a fundamental classification of

the possible graphs.  That is, the distinct ways in which a set of nodes can

be connected to form a cyclic graph have been calculated in advance. To apply

these calculations to actual formulas, a number of simplifying steps are intro-

duced:

    1.  Analyze the ring into its paths and vertices (branch points). The    .A?.//

classification then depends on the set of branch points, the atoms which zre

triply connected.  Organic rings rarely have more than three branches at any

point; instances of four branches (usually called "Spiro" forms) can be accommo-

dated by exception.  H atoms and other substituents attached to the ring are

ignored.

    2.  Produce a general classification of connectivity diagrams, the trivalent g2,/20
graphs.  Section 2.2 reviews how the set of trivalent graphs can be systematically

arranged without isomorphic redundancies.  With few exceptions, such graphs are

most conveniently presented as chorded polygons. (Hamilton circuits),

Polygonal graphs are relatively easy to compute, but they fail to show many
                                                                u.z, /22,

of the symmetries of the figures.  This is dramatized by the two isomorphic

polygonal representations of the bi-pentagon.

BI-
PENTAGON


Furthermore, a few graphs lack Hamilton circuits, and thus cannot be represented

as chorded polygons.

2 ,. ; ,2...z

                                                  .z I ix.3

   3.  Map the paths of the chemical graphs on the diagram, according to the

canons detailed below.

   An example will be introduced at this point to help illuminate these     ;2 , / t/L"


detailed rules.

   To recapitulate, the linear paths and the vertices connecting them are   2-/v,/


first identified.  The vertices are simply the branch points, i.e., the atoms

with three or more links to the rest of the ensemble.  For these purposes a

double or triple bond is a single link.  The paths are then the intervals

between the vertices.  A path may be a simple link or a linear string of

tandemly linked atoms.  For example, marking the paths of pyrene (a) gives the

diagram (b)

PYRENE

(a)              (b)

(cl

(d)

which is readily recognized as isomorphic to the prism (c) and its formal

????? ??? o  The isomorphism of (b) with (c) could also be established algo-   ,.&? A/3
rithmically by systematic permutation of the incidence matrix of the graphs,


(c) represents the essential idea of topological mapping. It then remains

to describe a syntax for describing such a figure in a unique code in com-

putable format.  Part II concerns itself only with the possible vertex groups,

leaving the mapping of the paths to Part III.


THE TRIVALENT CYCLIC GRAPHS

(The non-separable connections of n trivalent objects)

   Each link must terminate in 2 nodes; each node has 3 incident links.    ..z * z&i


Hence there will be 3n/2 links and the order n must be even.  The following

development treats n from 0 to 12 in detail, but could be generalized

indefinitely.  The main objectives are to indicate

          (1)  all the possible graphs

        (2) isomorphisms of superficially different graphs

         (3)  symmetries within a graph

          (4)  rational description of each item

          (5)  rational ordering of the graphs

         (6)  rational numbering of the vertices and paths

          (7)  compact, computable notation for each feature

                                                     .z-z?A

        Several computer programs have been applied together with substan-

tial manual effort to meet these objectives.  The results are mainly summarized

in the accompanying diagrams.

Any trivalent graph of a given order is found to represent either

      (1)  a polyhedron of the same order (i.e. a planar graph

       nowhere separable by < 3 cuts),or

      (2)  a compound graph, the union of two planar graphs of

         lower order, obtained by cross-reuniting a pair of

        cut edges, one from each graph, and thus somewhere

        separable by 2 cuts, or

     (3)  a gauche or nonplanar graph, also called skew.


    Polyhedra, including the degenerate forms with 0 vertices (the circle    2 ;L. .d

with two virtual faces, no solid angles) and 2 vertices ("bicyclane", three

virtual faces), are thus fundamental to the general development.  For their

formal computation we have relied on the conjecture that every trivalent

polyhedron has a Hamilton circuit, i.e., a circuit

of paths that traverses each vertex just once. On

this basis, any polyhedron can be projected as an n-

wn, with n/2 chords planted across all the vertices.

(Therefore, graphs with a Hamilton circuit may be

called "polygonal".)  This conjecture has been


attributed to Tait 113 by Tutte[" , who has found

a counter example which has, however, 46 vertices [21.

While no tangible examples are known to have been

missed, a sounder topological theory of polyhedra could beboth reassuring and

more elegant (see 2.5).

The trivalent polyhedra of from 0 to 12 vertices have been calculated in  .z `Z.-Y/

this way, and various representations of each of these are shown (Fig. 2T.5).

They.have also been checked for n c 12 by the traditional method of adding an

extra edge in all possible ways to each of the faces of the polyhedra of order

n-2.

The polyhedra were extracted as a subset of the chorded polygons.  That   2 2 3 2

is, all permutations of n/2 chords across an n-gon were systematically con-

sidered.  This representation has the advantage that its elements remain

invariant under manipulations of the polygon, e.g., rotation of the vertices.

The program then demoted the graphs that had doubly connected parts, that is,

that were unions of two graphs of lower order.  Al.1 graphs were tested for

isomorphisms by systematic tracing of the alternate paths to find other possibly
distinct Hamilton circuits~ i.e., alternative representations as chorded polygons.

Comparisons are made on the basis of span lists, i.e., cyclic lists showing the

*This is best accomplished by 2.90


span of the chord from each vertex (cf. 2.30).

7.

The canonical form of the span list is the lowest numerical value*        --.
                                                       under

the permitted operations of n-fold rotation and reflection.  For the most part,

the symmetries could be prospectively anticipated to make the program more

efficient.  The graphs were scrutinized for planarity (Kuratowski's criterion,

see 2.25).  The planar graphs were then candidates for manual construction of

polyhedra.  We conjecture that topological symmetry can always be carried over

into the geometrical symmetry of the construction of the polyhedron. The assign-

ment of solid angles is, of course, arbitrary.

*****

*2.2331

   In the computations here, the program as it evolved included a particular

interpretation of the span.  This is the shortest interval between the nodes in

either sense; when ambiguities were discovered, they were resolved by adding a

low order bit (say l/2) to the value for the retrograde sense. Hence for the

prism the span values are:


Compound Graphs.  Unions of smaller graphs have been developed in two ways. 2 2y'

The program for permuting chord lists on the polygon produces all the compound

graphs with Hamilton circuits. However, many compound graphs are non-polygonal.

The only cases relevant to chemical graphs (i.e. with less than 38 vertices!)

can be composed by a bilineal union of two circuits, when a single circuit is

lacking.  The theory of non-Hamiltonian polyhedra has some mathematical, if no

chemical interest, and must be included in any general classification of graphs,

as discussed in an appendix (2.72).

   Gauche Graphs.  A gauche or non-planar graph is one which cannot be   .d 22-c

represented on the plane (nor, therefore, by projection as a polyhedron),

without some edge crossing over another.  Kuratowski showed that any gauche

graph must contain either (a) or (b):

Do such graphs play any role in chemistry?

(a)

(b)          (cl

(d)

  In fact, none of the 11,524 rings in the Ring Index is gauche; consequently,

except for 6CCC, the gauche graphs have been deleted from the figures in this   2.2 3-z


report.  The consideration of 6CCC as a polyhedral derivative will illustrate the

difficulties and possibilities of formulating a gauche structure.  Fig. 2.25a

can be passed over as a pentaspiro formation already of unreasonable, though

perhaps not unattainable, complexity.

Figure 2.25~ shows 6CCC as an internally chorded tetrahedron. That is,  2 2. J-3

a gauche graph must have an additional path within an already tightly caged


structure.  Figure 2.25d illustrates a possible candidate to fill this hiatus in

topological chemistry.

  The obligatory nonplanarity of the gauche graphs should not be confused  2 zJ-ii/'

with the optional drawing of crossed paths in representations set out as alter-

natives to a planar mesh (v. Part 1II);a gauche graph has no planar mesh.

Interpretive Coding of Vertex Group Diaprams.                       2 2 J-J--

  The chord list of any polygon can be abbreviated to give an interpretive

code:  (1) letters of the alphabet, A to Z, stand for spans from 1 to 26, (2) a

chord is mentioned only once, when either end is first encountered, since the

span fixes the location of the other end.  Thus the prism,  whose chord list is

234234 becomes 6BCB, the underscored figures referring to chords denoted by
  --

previous digits.  Actually the last character is redundant, being fixed by its

predecessors in the construction.  Thus any polyhedron with n vertices, if it

has a Hamilton circuit, can be constructively and compactly denoted with a

code of only (n/2-1) characters.  These codes, lacking invariance under rotation,

are treacherous for the recognition of canonical forms and therefore play no

role in the computation, being translated at once into the complete span list.
These codes have also been shown on Figure 2T.5 for illustration purposes. The
syntax will be evident from the examples and from the dissection of Figure 2T.20.

  Ordering. The graphs are ordered by the following rather arbitrary     2260

principles.  There are however designed to facilitate matching of codes with

established lists.


    1.  Polygons.  The polygon is oriented so as to minimize the numbering   2.2-z/

of its span list (cf. 2.2331). Within each series, the order is then given
by the compact code generated from this number, v.s., 2.255. If two or more


polygons are isomorphisms, all are shown; the canonical choice among them

has minimal coding.

        A.  Polyhedra are displayed first.


        B.  Then unions with polygonal representations.                     .2  .% i .2

    2.   Non-polygons.  The polygons are projections of Hamilton circuits on a

circle.  When no single circuit captures all the nodes, the graph may be

dissected into two disjoint circuits joined in a bilineal union (for further

mathematical curiosities see 2.72).  The canonical dissection creates a

maximum couple of circuits, the larger taken first.  The value of a circuit is

determined by its

      order (number of nodes)

      compact code:  chord list    (2.255)

     edge designated for splicing in bilineal union.

The coding follows the form C l:nl,n2:C2 where Cl and C2 are the component

circuits; n 1 and n 2 are the spliced edges.  The set of known examples for

n=8, 10, 12, as given in 2T. 4 , will clarify the notation.


   Numbering of Vertices and Edges.  Before defining the mapping of paths     2 -A-

we must consider the numbering, i.e. ordering the sequence of vertices and paths.
This issue is closely connected with canonical orientation of the diagram. A
natural linear order for the parts of a polyhedron is not always self-evfdent.

The polygonal representation, whenever one exists, suggests one approach. We

must still select an orientation of the polygon, which may offer a choice among

n-fold rotational and 2-fold reflectional permutations.  For the present treatment

we adopt the minimum span list (See 2.2331).  Thus, some possible representations

and notations for the prism are:

3      4          SPAN LIST   -  234234

                  CHORDLIST   -  6BCB
2                5

1      6

INCIDENCE MATRIX

2 3 4 5 6
-7-J :

1       3
  114
     15

FACE INCIDENCE (DUAL GRAPH) - BDE ACDE BDE ABCE ABCD        B C D E
                                                      1     11A
                                                     1llB
      1
                                                       11c
                                                            1D

FACE LIST, VERTICES - 123 2345 456 1346 1256

FACE LIST, EDGES -  abg bcdh dei efgi aefh

INTERCHANGE GRAPH  - bfgh acgh bdgi cchi dfhi    bcdefghi
                                          1          111      a

abgi  abef  abde cdef            1          11 b
                             1       1 lc
                                1        lid
                                   1     lie
                                 1 lf


Of these various representations, the Span 1s is brief and,being invariant     s<3;L:


under rotation,  easy to permute.  We therefore denote each graph by its span

list in minimal form and label the vertices in the corresponding sequence.  Thus

(234234) = (342342), of which (234234) is minimal.   Hence

3(!Q) - 4@ = 2@
  2     4                   3    2                     4    3

The numbers above are the span, not tne vertex values.

5          2

Vertex Labels

z .?J

  The vertices being numbered, the path list is in the order of the vertex

couples, the polygonal circuit being taken first, then the chords.  Thus the

nine edges of the prism are, in order, 12, 23, 34, 45, 56, 61, then 13, 25 and

46.   Caution:  the polarity of each path follows this numbering.  The same rule

is applied to "self-looped edges," or "slings", i.e. chords with a span of 1.

Examples:

    6

5

3

6BCB

6

5  9     1
0
4 *

             3

        6AAA
Edges


   Numbering of Vertices and Edges.  Before defining the mapping of paths     ,p -2ir


we must consider the numbering, i.e. ordering the sequence of vertices and paths.

This issue is closely connected with canonical orientation of the diagram. A

natural linear order for the parts of a polyhedron is not always self-evident.

The polygonal representation, whenever one exists, suggests one approach. We

must still select an orientation of the polygon, which may offer a choice among

n-fold rotational and 2-fold reflectional permutations.  For the present treatment

we adopt the minimum span list (See 2.2331). Thus, some possible representations

and notations for the prism are:

3      4          SPAN LIST   -  234234

                   CHORDLIST   -  6BCB
2                5

1      6

INCIDENCE MATRIX

2 3 4 5 6
11       11
   1     1
-----I 2
      1       3
        114
           15

FACE INCIDENCE (DUAL GRAPH) - BDE ACDE BDE ABCE ABCD        B C D E
                                                    1     11A
                                                   1llB
      -7
                                                         11c
                                                              1D

FACE LIST, VERTICES - 123 2345 456 1346 1256

FACE LIST, EDGES -  abg bcdh dei efgi aefh

INTERCHANGE GRAPH  - bfgh acgh bdgi cchi dfhi    bcdefghi
                                            1         111 a
              abgi  abef  abde  cdef            1          11 b
                                               1       1 lc
                                                  1       lld
                                                 1 lle
                                                     1 lf


Of these various representations, the span 1% is brief and,being invariant     2,3z

under rotation,  easy to permute.  We therefore denote each graph by its span
list in minimal form and label the vertices in the corresponding sequence.  Thus

(234234) = (342342), of which (234234) is minimal.   Hence

3(!gfi - J=Jy = 2b$$
  2     4                  3    2                    4    3

The numbers above are the span, not tne vertex values.

6      1


5 43 2



  4      3

Vertex Labels

                              z .?;/

  The vertices being numbered, the path list is in the order of the vertex

couples, the polygonal circuit being taken first, then the chords.  Thus the

nine edges of the prism are, in order, 12, 23, 34, 45, 56, 61, then 13, 25 and

46.  Caution:  the polarity of each path follows this numbering.  The same rule

is applied to "self-looped edges," or "slings", i.e. chords with a span of 1.

Examples:

    6

5

  3

6BCB

6

  3

6AAA

Edges


   Numbering of Vertices and Edges.  Before defining the mapping of paths     ,7 -3r

we must consider the numbering, i.e. ordering the sequence of vertices and paths.

This issue is closely connected with canonical orientation of the diagram. A

natural linear order for the parts of a polyhedron is not always self-evident.

The polygonal representation, whenever one exists, suggests one approach. We

must still select an orientation of the polygon, which may offer a choice among

n-fold rotational and 2-fold reflectional permutations.  For the present treatment

we adopt the minimum span list (See 2.2331).  Thus, some possible representations

and notations for the prism are:

    3 4
c3        SPAN LIST   -  234234


                   CHORDLIST   -  6BCB
2                5

1 6

INCIDENCE MATRIX

2 3 4 5 6

FACE INCIDENCE (DUAL GRAPH) - BDE ACDE BDE ABCE ABCD        B C D E
                                                  1     11A
                                                     1llB
      -7
                                                         11c
                                                              1D

FACE LIST, VERTICES -  123 2345 456 1346 1256

FACE LIST, EDGES -  abg bcdh dei efgi aefh

INTERCHANGE GRAPH  - bfgh acgh bdgi cchi dfhi    bcdefghi
                                          1         111 a
              abgi  abef  abde  cdef            1          11 b
                                               1       1 lc
                                                   1        lld
                                                 1 lle
                                                   1 lf


Of these various representations, the span list is brief and,being invariant     2-32


under rotation, easy to permute.  We therefore denote each graph by its span

list in minimal form and label the vertices in the corresponding sequence.   Thus

(234234) = (342342), of which (234234) is minimal. Hence

3J--p - 4@ = 2@7J
  2     4                   3     2                    4    3

The numbers above are the span, not tne vertex values.

5          2

Vertex Labels

                              2 .?J

  The vertices being numbered, the path list is in the order of the vertex
couples, the polygonal circuit being taken first, then the chords.  Thus the

nine edges of the prism are, in order, 12, 23, 34, 45, 56, 61, then 13, 25 and

46.  Caution:  the polarity of each path follows this numbering.  The same rule

is applied to "self-looped edges," or "slings", i.e. chords with a span of 1.

Examples:

    6

5

4


    3

  6BCB

    6
5 9     1
0
4 *

  3

6AAA

Edges


  With non-polygonal forms the numbering of the united circuits must be     2 3/r-


unified.  The smaller circuit retains its original numbering, including the

uniting edge joined to the lower node.  Then the numbering of the nodes or edges

of the senior partners follows in sequence.  Example:

  1
Q

8


Quadrivalent Vertices.   Some organic molecules of considerable interest   d-z -f C'

have one or more 4-valent nodes, needing special provisions in our scheme.  The

system so far developed can be most advantageously exploited by treating an n-valent

node as the collapse of some subgraph on which n edges are afferent.  Two possibi-

lities for a 4-valent node (a) are

C         d

   0-i
c/ \d

(a)            (b)

cc>

The second (c) has the advantage of adding only one virtual node per 4-valent
center. guadrivalent centers will therefore be treated as collapsed edges of a

parental trivalent graph.  The adjacent edges (abed) can be divided in three

different ways:  ah/cd, ac/bd and ad/be, hence there may be as much as a three-

fold ambiguity in the choice of parental graph.  This will ordinarily be less

on account of symmetry.                                               2.41

  The ambiguity can be fully resolved by the following canons of choice of

parent graph.


    1.  Avoid a separable graph.  Hence c ] is related to ;j)  and not c- yJ *

    2.  Avoid a gauche graph if possible.

     3.  Avoid a nonplanar graph if possible.

    4.  From the remaining possibilities, choose the graph which, in canonical

form and listing, stands lowest.  For an example, n = 9

may go into

(a)

(b)

BCDDB             BCCCB         [CAUCHE 1


(a) and (b) are readily reduced to their canonical form.  (c) is recognized

as gauche (see the graph 6CCC as the left part of the isomorphic (c'>-- the

numbering of a Hamiltonian circuit is displayed to help along), and therefore

disqualified.  In the tables, (a) and (b) are already known as BCDDB and

BCCCB respectively.  By canon 4,  the choice is BCCCB.

   The encoding follows the principles for mapping other paths to be detailed

in Part III.  However, the specification of contracted edges (Spiro fusions) is

given at a separate, first level of priority , to bring structural homologues

under a common heading.  Where symmetries require a choice, the Spiro fusions

will be mapped on the edge list so as to maximize this vector. I.e., they are

placed as early in the list as possible.  The numbering of vertices and edges

is retained as given in 2.3.  That is,  a virtual node.remains in the list.

    The present example becomes

_ j" _'

__' I ,

i.e., the Spiro fushion is mapped on the 3rd edge of the circuit.  The coding is

a reasonable one to mark the vertex group for these figures.  Additional examples

are summarized in Table 2T.7.  Applications to complete graphs are detailed in

Part III.  The program contains a sufficient list of canonical forms and synonyms

to expedite the translation of any vernacular input codes.  These manipulations

are not particularly difficult to program, but as already demonstrated can be

quite tedious by hand.


                                                      2 3-c
     Planar Mesh Representations.  Besides the isometric perspective and

polygonal representation, any polyhedron can be represented as a planar mesh.

Consider the polyhedra projected on a sphere.  Then choose any face for a base

and expand it, flattening the rest of the sphere to an enclosed plane. This

operation shows that any polyhedron has a planar representation (no edges

crossing); furthermore, any distinct face will give a different appearance

when expanded.  Usually the largest face will give the most nearly conventional

representation.  When the mapping is expanded, this will usually be more nearly

reminiscent of the usual structural formulas than the more abstract figures so

far presented.

The isomorphic variants of planar meshes obtained by choosing alternative

faces as the base (see Fig. 2.51) are generally very unfamiliar, pointing up the
                                                                    .5-/

importance of a canonical representation.

ABC             BCDE
OR              OR
A IJ             FGIII

IOA3

I OA4A

DEFG

IOA4B

ABEFIJ
OR
ACDGHJ

IOA6

   IOA6
WITH MAPPING OF
BENZOPERYLENE


Reconstruction of planar mesh from Hamilton circuit representations.

The polygonal representations of figure 2T.4 and 2T.5 are undoubtedly con-

fusing owing to the intersection of chords belonging to different faces. A simple

algorithm can help to resolve these figures;  it is also useful for the computer

reconstruction of planar maps, closer to the chemist's customary models, from

the canonical codes.

The main idea is to regard the polygonal form as projected on a sphere,

the polygon forming the equator. Then, for a planar map, the chords must be

classified into two sets, one for each hemisphere.  Within either hemisphere, no

chords intersect.  The visualization of these structures still requires some

practised imagination, especially to avoid the identificaiton of the Hamilton

circuit polygon with any face of the polyhedron.  However, as any face will be

bounded by edges from the cirucit and from one hemisphere, the marking of faces

is facilitated for chemist and computer alike.  In practice the computer should

carry all the burden of these transformations.

                                                                           &. 3 -/
     The grouping of chords is quite simple. The assignment of N vs. S

hemisphere is, of course, arbitrary; the first chord is assigned N. Then each

succeeding chord is tested for intersection with the N set so far.  If not, it

is added to the N set.  If it elbes intersect,  it should be added to the S set.

If it also intersects a chord already in the S set, the graph is non planar.   Indeed

this is the most effective algorithm for the purpose.

Planar meshes come directly from the chord groupings. The chords of one

hemisphere are merely brought outside the polygon.  Thus, for the pentagonal wedge,


BCCB


which takes only a topological deformation to yield

recognizable  as

   .        \
   .
   .           \
   .
   .            \
   .
r3
   .              \
        .' *
            .'
`\        .
          :
   \ -
      \ \

When the map is a 2-connected union an obiious ambiguity may arise, some chords

intersecting with neither of the remaining sets.  This does not impair the con-

struction of a planar mesh.

or

could be

etc.

The rule would be: place a chord in the S hemisphere (inside) if it is ambiguous.
This ambiguity is probably the main source of disparity in conventional chemical

symbolism; related to it is the choice of face to circumscribe  the map.


Nested parenthesis notation and combinatorial generator.

   Since the chords of one hemisphere do not intersect, the labels that signify

their start and end have the properties of nested parentheses, the matching of left

and right parentheses being implicit in the description.  For the two hemispheres   2. SC51

of BCCB we have pJ = )Q) + (Q
and superimposing the parentheses and brackets we have a descriptive formula

     ([)(I[)3

This is economical in the computer program since it codes the signs as 2-bit

numbers, the formula becoming

      02103213.

Such a formula can be translated into a usable mesh diagram on sight:

          1         I
   -2-i-o--3

It is also the basis of a rather more efficient generator program than the one

mentioned in 2.232.  Besides the economy of compact representation of the codes

as quaternary numbers, it is easy to restrict the generator to minimize fruitless

efforts with meaningless codes (e.g., extra right parentheses) and redundant forms

(interconversion of () and [I; some rotational symmetries).  The notation is

already explicitly limited to Hamiltonian planar maps.  For certain investigations,

additional restrictions like absence of triangles, cyclic connectedness at a level

of at least 3 (i.e. polyhedra), 4, or 5, and other features can be rather easily

added.  However, the output is replete with isomorphisms, for which the technique

of      2.23 2     is still the most efficient.


Further Developments in the Theory of Trivalent Graphs.

Polyhedra.  Since the above material was composed and most of the computations


run, some additional contributions in the literature have come to light.

      It was especially surprising that the enumeration of the polyhedra had

not been worked out already in Euler's time or earlier, in view of classical     .% ,$ /

insight into the five regular polyhedra (of which three, the tetrahedron, the

cube and the dodecahedron are included in our trivalent graphs, n4, ng, and n20

respectively. In 1900, however, Briickner%onstructed the trivalent polyhedra

for n up to 16, and we could confirm the equivalence of his set with the results

of our computer programs through n = 12.

      Little additional work has been done on this problem, except by Briickner.
However (and independently of the present studies!) Grace has just published a    ;T.-, so

dissertation on the computation of the polyhedra through n =I8 (Grace, 1965). This
work faces formidable problems in testing for isomorphism (18! = 1015)-wise

permutational searches being prohibitive.  Mathematical theory evidently still

lacks an analytical approach to this problem.  Grace then used a conjectural

criterion of isomorphism, "equisurroundedness".  According to Grace "Equisurrounded-

ness is a necessary but not a sufficient condition for isomorphism. The necessity

is obvious...."  He gives a counter-example with 17 faces to show the insufficiency.

It is therefore uncertain whether he may have retained an incomplete list of

polyhedra, as it is unknown whether some smaller polyhedra than with 17 faces

may be equisurrounded with, but not isomorphic to, members of the list that has

been retained.  Grace did find some forms that Briickner had overlooked.

      The polyhedra through n = 18 have been verified to have Hamilton circuits,
including the classes n14, n16, and n18 as listed by Grace.   It should be remarked   .. 7 &: 3


that the test for isomorphism (see 2.232) of polygonal graphs is relatively efficient,
                                                                     .
since << 2" operations (contra n!) can establish (a) whether a graph has a Hamilton

circuit and (b) if so, establish a canonical form for comparison with other graphs.


This test could be applied to Grace's for generating polyhedra program to discover

any polyhedra smaller than n q6(Tutters example) that might lack a Hamilton circuit,

(see 2.230) and a more rigorous criterion of isomorphism than equisurroundedness

can furnish.

The task of scrutinizing polyhedra for Hamilton circuits is simplified

considerably by the reducibility of a triangular face.  Consider a trace of a  z, Gf

Hamilton circuit at its first incidence on a triangle:

Plainly if all 3 of its nodes are to be visited, it must be at this occasion. A

path -1-2 without 3 would leave 3 stranded, i.e., would make a Hamilton circuit

impossible.  The complex -123- is therefore tantamount to a single node.

ORDER = N

ORDEK = (N-2)


Thus, if the (n) graph has a triangular face, and a Hamilton circuit, some (n-2)

graph will likewise have a Hamilton circuit. Without formal proof, we assert

that if (n) is a polyhedron, so is (n-2).                                     ." 2, .,-
                                                                           ..- , ir -'
     By induction we may then pass over (n)-rojvhPdra that have any triangular

face , provided we have scrutinized all the (n-2) cases, which can be handled in

part by the same process.  As shown by the following table, this argument reduces

the work for the polyhedraup to 18 vertices from 1555 down to only 55 cases.

N


4


6


8


10


12


14


16


18

Total Polyhedra

1

  1


  2


  5


14


50


233


1249

Non-triangle-containing
    Polyhedra

0

0

1

1

2

5

12


34

2. G-B

Total n 2 18                1555

-

55


    The listings of tables 2T.2  anticipate the polygonal graphs through

12 vertices, that is 8 faces, (or 7 rings within the meaning of the Ring Index).
From Grace's work we can readily enlarge this anticipation to 18 vertices, (11

faces or 10 rings) but have not made the extensive enumerations called for.     .;3.d-

The count of unions and particularly of gauche graphs increases even more

rapidly than that of the polyhedra.  On the other hand, the notational system

will accommodate any polyhedron that has a Hamilton circuit, as well as unions

of such polyhedra; such structures can be coded as they are defined without

being anticipated in advance.  The generator would then be confined to an

empirical list  of previously discovered forms.  This may be a practical

necessity for the highest order forms in any case, where the rapidly increasing

number of possible arrangements contrasts with relatively few realizations.

    The most complex rings, in practice, are related to polyhexacyclic           L-
                                                                           -*

hydrocarbons.  This special class can be accommodated by another approach,

elaborated in Part 6.  This involves the mapping of the polyhexacycle on a

selection of "tiles" from a continuous hexagonal tessellation or mosaic. An

enumeration of these forms is also given in Part 6.


Symmetry classification.

     The symmetry of the vertex group plays a central role both in mapping   ..z -/<:.

known structures and in the generation of non-redundant lists of hypothetical


structures.  The essential problem is that the same topological relationship

may have many alternative representations, which is to say that the diagram can

be manipulated so that it is self-congruent. If the vertices are labelled,

different sets of vertices will describe the same figure. E.g.,

Since we are dealing with topological groups, not rigid bodies, the symmetries

carry even further, i.e. the tetrahedral cases are not distinguished (stereo-

isomerism being dealt with at another level).


The polyhedral representations generally make the set of symmetries   ,c. 7'L/

self-evident (which the planar ones sometimes do not).  For example, the prism

has 12 equivalents

-- --
>
r   3 rotations

  !


-- +--
I        2 rotations


   1 2 reflections

while its Hamiltonian polygon

displays only 4.

Although not a profound task, the manual enumeration of the symmetries, say

for table 2T.2, would be a tedious one and an algorithmic approach would be

preferred.

   One approach is to generate the whole symmetric group, Sn, the n!

permutations of the vertex codes, and test each of these for congruence with

the canonical form.  But this is almost prohibitively costly for n - 10, as lO! =

3,628,800 trials, or probably about one minute of computer time per set.

     Instead we can rely upon the set of Hamiltonian circuits, where they   2 7`9.3



exist.  Each symmetry operation will generate a corresponding representation of

a Hamilton circuit.  Consequently the set of symmetries will be included in the

set of Hamilton circuits.  These can be generated by a binary search of << 2"

trials, far less than the n! of the whole symmetric group.  In fact this list

of Hamilton circuits was saved from the initial computation of table 2T.2 for

use as the input data of this calculation.


The algorithm can be summarized                           #Z. 7/

1.   Take E as the canonical form from table 2T.2.  Convert the chord list to an

incidence matrix (connection table) of the n vertices with one another.

2.   Test E for its symmetry on the plane.   That is, test E under l(l)n-1 steps

                                         123...n

of rotation of its indices [the permutation cycle (234 . . . ,)I before and after

reflection, ( 123..n
     n..321)'  When the permuted incidence matrix becomes congruent with

E, a symmetry operator is revealed.  This set of operators is saved.

3.   Each Hamilton circuit is tested for potential congruence with E under


rotation and reflection.  The isomorphisms (indicated in table 2T.2) cannot be

made congruent to E and are rejected.  The congruences are saved as equivalents

under symmetry.

4.   Each of these is also subjected to the operators found in step 2.

5.   The list is sorted and redundancies are removed.  This can also be done

prior to 4 if the list is a long one.

6.   The list now contains all of the symmetries expressed as permutations.

Further classifications can be made, as indicated, on this list.  For many

purposes it can be used as is.



Example.  Consider the prism, BCB



     a.  This is readily translated into


                         --
        123456 plus 13,25  and 46.

        2   cc>


(B) 1          3
CD 4 (B)




        5

b.  E is of course 123456.  The symmetries of rotation (C,) and reflection
(I) are readily found and give

123456     456123     654321     321654.

    2

3       1

4       6

1  - i
:. , , /'

c321654]


7.  Our program gives the following additional Hamilton circuits.  For efficiency,
the search was initialized at vertex 1 and considered only the paths 12 and 13

as candidates for the first trial choice.  That is,  the rotation and reflection

operations were anticipated.  Hence the circuits as found are potentially, not

actually, congruent with E.   At this point they are

                 125643     134652     132546.

The first two require a rotation; the last is already congruent.  When rectified

we then have

312564                                           2  / ,' ,,i-

312564      213465      132546

8.  These are used as operands under the operators found in 2.  Together with E

we then have

       E        456123        654321        321654
   312564       564312        465213        213465
   213465       465213        564312         312564
   132546       546132        645231         231645

9.  After sorting and weeding out we have the 12 cases.

123456    213465     312564     456123     546132     645231

132546    321645     321654     465213     564312    654321

For small n of course we can more readily operate on a visual image of the prism

at speeds that compare with the computer.  But recording the results becomes a

bottleneck in more extensive work.


   General Svstematics of Graphs.  Composition of graphs from Hamilton


Circuits:  2-connected graphs.                              2. 72

A more general approach to the description of circuit-free graphs has

been devised based on the level of connectedness of the graph, i.e., the

least number of cuts needed to separate the graph.

The cases of chemical interest are all 2-connected, and have already been

discussed in section 2.262.                               2.73
   Canons of Analysis.  A 2-connected graph found to be circuit-free is

subjected to trial dissections of its bilineal unions, designed to show a con-

struction under the following criteria.  The principle of analysis is to

obtain a dissection of the graph into

    1.  A minimum number of circuits


    2.  At the lowest level of connectedness.

In effect, the dissection maps the circuits of the graph on to the nodes of

a "hypergraph."  If a Hamilton circuit is present this hypergraph consists of

a single node,  Otherwise it may be a node-pair (i.e. a pairwise union of

circuits) or in principle a more complex tree or even a generalized connected

graph.  The hypergraph is then evaluated according to the same principles as

laid out for chemical graphs -- the nodes being the circuits; the edges being

the sets of circuit-joining edges.  We can therefore add the criterion:

    3.  Giving the maximum valued hypergraph.
  The evaluation of the hypergraph may entail searching its set of circuits,

as may be done recursively to any depth.


  This analysis leads to some predictively useful principles concerning    2. qf

the occurrence of non-Hamilton graphs.  A given circuitable graph is readily

analyzed for the presence of three kinds of edges (1) the most usual edges

participate in some but not every circuit (2) "must-edges" participate in

every circuit, or (3) "non-edges" participate in no.circuit.

  A bilineal union in which a non-edge of either or both component graphs

is spliced then forms an HC-free graph.                            ,z. 73.-

   The same approach can be used for 3-connected graphs.  In this case, a 3-cut

residue is obtained by extracting one node from a graph.  If one of the cut

edges is a must-edge, it will retain this property in its compositions. Thus,

in Tutte's example, replacing 3 nodes of a tetrahedron by a 15-node residue with

a must-edge results in a 46-node circuit-free graph.  (Fig. 2.23 ).

  There is no present compulsion to rigidify the notation for such

complex graphs; one suggestion is implicit in the diagram:

(38CGDIGDIDGE*CD:231:C*DIGDFD)


  This 38-node graph is the same as 2.78d; the polygons are oriented in

canonical form.  The *'s signify the extracted notes whose removal leaves the

3-cut graphs; the 231 specifies the splicing of the cut edges.  Note that

the subgraphs to the right and left of the dashed lines are the same.

The construction shown follows the rule of dissection into maximum 3-connected

circuits.

  This graph which is the same as 2.78d is almost certainly the       a?,78


smallest non-Hamiltonian polyhedron;  it is known to be the smallest which

is cyclically 3-connected. All candidate graphs n 2 24 have been

explicitly examined.  Its construction may be clarified by noting the must-

edge (marked by arrow in 2.78a).  A residual 3-cut graph can be planted, as

shown, in 2.78~ and 2.78d in configurations  inconsistent with must-edges in these

figures.  2.78~ is Tutte's 46-node graph, already figured at 2.23. The dashed

lines on 2.78d correspond to those on 2.77.

   ' XI            .
     `\


0 ('        \    o
@
               ?
      ?
   ?            ? ?
? ?                   ?


Coding and Reconstruction of Hamilton Circuits

;`. YO

Each graph is represented as a Hamilton circuit projected on the boundary

of a regular polygon with n vertices. Joining these 11 vertices are 5  chords,

since each vertex is trivalent.  The locations of these chords are specified by
k characters, integers being replaced by the alphabet to obviate punctuation*.

    To reconstruct the graph:

    1) Draw the n-gon

2) Start at an arbitrary node and draw a chord whose span corresponds to

the first character

3) For each successive character, move to the next unoccupied node.
                                                        -

Hence, the steps for 6BCB are:

occupied

6         6~         ~Bc         6BCB

*A   1       F   6       K   11       P   16      U    21

B   2       G   7       L   12      Q    17      v    22

c   3       H   8       M   13       R   18      W    23

D   4      I   9       N   14      S    19      X   24

E   5      J  10       0   15       T    20      Y    25


Appendix:

A1gorith.n for finding hamilton circuits of a cyclic graph.

    This is illustrated for an undirected, trihedral graph but should be

generalized without difficulty in an obvious way.  Tne input is a description

of the connectivity of the graph. T>e essence of the routine is to build

a table of sets of edges so that just two edges incident in each node appear

in any row of the table.  Tne first node is chosen arbitrarily.  its three

incident edges are marked current and open.  T?ne circuit-fragment table

is started with three rows by listing the 3 pair-wise choices among the

current edges.

   1.  Select an open edge.  The two adjacent edges become the trial

      edges.


    2.  How many trial edges match the current list:  none, one, or two?


              a.   If none match, close the selected edge and replace

          it on the current open list by the two trial edges.

          Scan the circuit-fragment table. Each row in which

         the selected edge appears is replaced by two rows, one

           for each trial edge.  Each remaining row is replaced

          by one row showing both trial edges. Go to 1.

           b.  If one matches, a circuit of the graph has been closed.
         Scan the circuit-fragment (c.f.) table contrasting the

          matched edge with the selected edge.  Each c.f. where

           neither appears is deleted.  If one of the two appears

            on a c.f., this is augmented by the trial edge.  If both

            appear, the c.f. +W stands as is unless a tracing of
       the c.f. shows it to be prematurely closed,whereupon it

              is deleted.  Go to 1.


C.   If both match two adjacent  f aces of the graph hsve been

    closed.  The Ireceding subroutine is revised in an

  obvious way to close o-&t both matched edges:  those c. f.



     rows are retained which are compatible with the indicated

            edge allocations.  Go to 1.

   The process is terminated when the  open  edge list is vacated. If

this leaves some nodes unused,no fiamilton circuit is possible.  Otherwise,

the final closure of circuit-fragments leaves a table of circuits.  This

must still be scanned to separate tn e Hamiltonian circuits from the set

of pairwise disjoint circuits.

  The efficiency of the algorithm depends on keeping the current c. f.

table as small as possible.  This is accomplished by a lookahead routine

which scans prospective choices of current edges to seek the promptest

closure of a face.

   For an example, Tutte's 1;6 node non-Hamiltonian graph has been searched

exhaustively.  This required a c. f. table of 12,477 rows consuming 29

seconds of a program on IBN 7090.  Searches yielding a11 the circuits of

other large Hamiltonian graphs required a comparable effort.

  This procedure may have some utility for studies on classification,

isomorphisns,and symmetries of abst ract graphs and other network problems

for w`nich the set of Hamilton circuits is often an advantageous approach.

A complete description of the computer program is available from the author.


REFERENCES

1.   Tait, P. G., Phil. Mag. (Series 5), 17: 30 (1884).
                                             -

2.   Tutte, W. T., J. London Math. Sot., 21: 98 (1946).
                                             -         (See also reference 3)

3.   Tute, W. T., Acta Math. (Hung.), 11: 371 (1960).
                                         -

4.  Bruckner, M: Vielecke und Vielflache.  Teubner, Leipzig, 1900.

5.   Grace, D. W., Computer Search for Non-Isomorphic Convex Polyhedra,
  Stanford Computation Center Technical Report No. CS15 (1965).


PART II.  GENERAL TABLES.

2T.l       Count of cyclic trivalent graphs.

2T.2

Symbolic listing of cyclic trivalent graphs n 2 12
and polyhedra n = 14.

2T.3

(Deleted)

2T.4

Nonpolygonal cyclic trivalent graphs n ( 12.

2T.5

Figures for graphs n 2 12 with chemical examples.

2T.6

Figures for polyhedra n 114 which have chemical
examples.

2T.7

Quadri-trivalent graphs.


2T.1

COUNT OF CYCLIC TRIVALENT GRAPHS

[and genera of known chemical graphs]

Vertices


   0


   2


   4


   6


   8


  10


  12


  14


  16


  18


  20


  22

  24

1. 26

  Number of
Chemical Rings+


     1


     2


     3


     4


     5


     6


     7


     8


     9


     10


     11


    12


    13

1 14

Polyhedra

With Hamilton Circuits                 Without Hamilton Circuits


      Unions           Gauche Forms
   (Planar)        (Non-Planar)         Planar Unions

I
I     1*
I

I
I     1*

0


0

0


0

I

1     1*                  1*                  0

I
    1*                  3*              If01
                                               _-------------
                                               l
    2*             10 [91           1
                                               I      3[01

                                         I
I    5 r41            37 [201           18[01
I                                               I
      :-- ----- - -_
   14 [3]        183j [35]          I
I                                                I    133[01
I--                               ---  ---  --
    -__,          I                                         _-.__     _.----- ___-         -
50 jf31    ;          [451                         [Ill

2333;[2] 1          [461                          [lOI
        I           I
12493,[5]        I
                  I          r251                          (51

1bl        /
          I         (211                           [41
I
1[11 ;         161                           [II
I           !
)21 ;         191                           [II
/__- _- -_I
101             1141                          [31

[Numbers in brackets are the count of genera of known examples from the Ring Index.] * signifies all.
Spiro forms are excluded from this count.

' Figures drawn herewith.
' Listed herewith
: According to Grace (1965).
This is one less than the number of faces of a polyhedron.


2T.2 SYMBOLIC LISTING OF CYCLIC TRIVALENT GRAPHS.

Polygonal Forms:  [Planar (polyhedral, unions), Nonplanar)

2T.20


2T.21


2T.22


2T.23

2T.24

n  = 4, 6,  8


n = 10


n = 12    Planar polyhedra and unions

n = 12    Nonplanar forms

n = 14   Polyhedra only (with Grace [1965]
      catalog number)

JJonpolygonal Forms:

2T.25      n = 8, 10, 12  Summary table,(see 2T.4).

The canonical form is shown first on each line.  Isomorphs (unrelated by
rotation or reflection) are then shown.  See 2T.254 for coding.


2T.20

POLYGONAL GRAPHS

POLYHEDRON

4 VERTICES

4A                BB

PLANAR UNION

46                AA

                6 VERTICES
POL'rHEDRON

6A                BCB

PLANAR UNIONS

60                 AAA
6C                ABB
6D                ACA

GAUCHE GRAPH

6X                ccc

               8 VERTICES
POLYHEDRA

8A                BCCB BDDB
8B                CECC

DLANAR UNIONS

8C                AAAA
8D                 AABB
8E                AACA
8F                ABCB
8G               ABDA
8H               ACDB
81                ADDA
8J                AEBB
8K                AECA
8L                BBBB

GAUCHE GRAPHS
                       ACCC
                       BDCC
                     CDDC DDDD


10 VERTEX   GRAPHS

2T.21

POLYHEDRA
  BCCCB BEFDB
  BCDDB BCEFC
  BDERB
  BDECC
  CFDEC

PLANAR UNIONS
  AAAAA
  AAABB
  AAACA
  AABCB
  AABDA
  AACDB
  AADDA
  AAEAA
  AAEBB
  AAECA
  ABBBB
  ABBCA
  ABCCB
  ABCDA
  ABDDB   ABEBC
  ABEAB
  ABEDA
  ABFBB

GAUCHE GRAPHS
  AACCC
  ABDCC
  ACCEA
  ACDDC   ADDDD   ADDEC
  ACDEB ADEF B
  ACEEA AEEEA
  ADECD
  ADFCC
  AGCCC
  BBCCC
  BCDCC BEFCC
  BDCDB   BEEEB
  BDDDC BEDCr) BEDEC
  BDDEB
  CCECC
  CDEDC DFDED
  CEEDD CFDDD CGDCD   DEEED
  CEEEC CGCCC   EEEEE

ABFCA
ACACA
ACECC   AECEC
ACFCB ADFDB
ACFDA
ADADA
ADBEA
AEBEB
AFCEB
AFDEA
AFFBB
AGBCB
AGCDB
AGDC 4
AGEBB
AGECA
BBBCB
BBCDB
BBEBB


12   VERTEX   GRAPHS

BCEFDB
BEBEDB
BEHECC

BDHOOB
BFBFCC

BFCFDC

DHFDFD

POLYHEDRA
  BCCCCB BFHFDB
  BCCDDB BCCEBC
  BCDEBB BCEBDB
  BCDECC BCFCEC
  BCDFCB BCGDBD
  BCFBEB BDFBDB
  BCFFBC BCCCEB
  BDECDB BEGEBC
  BOFCEB BDGEBD
  BDFDEC BEGECD
  BOGDEB
  BFBFBB
  CGEGEC CICCCC
  CHFCFD CIFCFC
PLANAR UNIONS
  AAAAAA
  AAAABB
  AAAACA
  AAABCB
  AAABDA
  AAACOB
  AAADDA
  AAAEAA
  AAAEBB
  AAAECA
  AABBBB
  AABBCA
  AABCCB
  AABCOA
  AABDOB AABEBC
  AABEAB
  AABEOA
  AABFAA
  AABFBB
  AABFCA
  AACACA
  AACECC AAECEC
  AACFBA
  AACFCB AAOFDB
  AACFOA
  AAOAOA
  AAOBEA
  AADFAA
  AAEBEB
  AAEFAB
  AAEFBC
  AAEFDA
  AAFFAA
  AAFFBB
  AAFFCA
  AAGABB
  AACACA
   AAGBCB
  AAGBOA
  AAGCOB
  AAGDOA
   AAGEAA
   AAGEBB
  AACECA
   ABBABB
   ABBACA

AB88CB
ABBBOA
ABBCOB
ABBDAB
ABBOOA
ABBE88
ABBECA
ABCBCA
ABCCCB
ABCCOA
ABC000
ABCEAB
ABCEOA
ABCFBB
ABCFCA
ABOACA
ABOEBB
ABOECC
ABDFBA
ABOFCB
ABDF DA
ABEAOA
ABEBEA
ABEEAB
ABEFAA
ABEFOB
ABFAOB
ABFBEB
ABFFAB
ABFFBC
ABFFOA
ABC080
ABCCAB
ABGDEA
ABGFBB
ABGFCA
ABHBCB
ABHBDA
ABHCAA
ABHCOB
ABHOAB
ABHOOA
ABHEBB
ABHECA
ACAACA
ACACOB

ABBOBC

ABCEBC

ABFCEC

ABGDBO
ABGOAC

ABGBCC

ABGBEA
ABGCEB

ABHDBC

ACAOBC

ACAOOA
ACAEBB
ACAECA
ACEBOA
ACECEA
ACFBOB
ACFCEB

ACGEBO
AECGOB
AGEBFC
AGECFO
AOBEDB
AOBFDA
ACGEEA
AGDCEB
AECCEA

AHFOBE
AHFDFA

AHFCFB
AOHFCB

ACFOEC
ACGBBC
ACGBOA
ACGCEA
ACGOEB
ACGEAC
ACHBBB
ACHBCA
ACHCCB
ACHCOA
ACHOAA
ACHDDB
ACHEBC
ACHEOA
ACHFBB
ACHFCA
AOAOOB
AOAEDA
AOAFBB
AOBGBB
AOCADA
AOGECO
AWABB
AOHEBB
AOHECC
ADHFOA
AEAFCB
AEBGCB
AEGAEA
AFAFAA
AFAFOB
ACBGBC
AGEGEA
AHBOEB
AHBEEA
AHBGBB
AHCGCB

AHECFC

AGOBFB

AHEBFB

23.22

AHOGDB AHEGBC
AHEAEB
AHEGDA
AHFAEA
AHFGBB
AHHBCB
AHHCDB
AHHDDA
AHHEBB
AfBBBB
AIBBCA
AIBCCB
AIBOOB .IIBEBC
AfBEDA
AIBFBB
AIBFCA
AICACA
AICECC AIECEC
AICFCB AfDFOB
AIDADA
AIDBEA
A fDFAA
A IEBEB
AIEFBC
A IEFDA
AIFFBB
AIFFCA
A IGBCB
A IGCDB
A ICODA
AIGEBB
A IGECA
BBBBBB
BBBCCB
BBBOOB BBBEBC
BBBFBB
BBCECC BBECEC
BBCFCB BBDFOB
BBEBEB
BBEFBC
BBFFBB
8BGBCB
BBGCOB
BBGEBB
BCBBCB
BCEKDB
BCHCDB KHDBC


2T.23

12   VERTEX   GALJCHE   GRAPHS

AAACCC
AABDCC
AACCEA
AACDDC
AACDER
AACF EA
AADECD
AADFCC
AAGCCC
ARBCCC
ABCDCC
ABDCDR
ABDCEA
ABDDDC
ABDDEB
ARDEEA
AREECD
ABEEER
ABEFCC
ABFACC
ABHCCC
ACACCC
ACCDDA
ACCECC
ACCEDR
ACCFDA
ACCGBB
ACCGCA
ACDDEA
ACDEDC
ACDEEB
ACDFCC

AEFBFB
AEGECF
AFAFCC
AFCEFC
AFGEFA
AGCCFB
AHCDFB
AHDGCC
AHECDE
AHHCCC
AIBDCC
AICDDC
A ICDEB
AIDECD
AIDFCC
AIGCCC
BBBDCC
BBCDDC
BBCDEB
BBDECD
BBDFCC
BBGCCC
BCBCCC
BCCDCC
BCDCDB
BCDDDC
BCDDEB
BCEECD
BCEEEB
BCEFCC
BCHCCC
BDCE CC
BDDCDB
BDDEDC
BDDEEB
BDDFBB
BDDFCC
BDEEDD
BDEEEC
BDEFCD
BDEGCC
BDFBCC
BDFFBD
BDGDCD
BEECEB
BEFCEC
BFFBFB
cccccc
CCDDCC
CCEDDC
CCEECC
CDEEDC
CDFEEC
CDGCDC
CDGDEC
CDHDCD
CEEEEC
CEFEED
CEFEFC
CEGCEC
CEGDED
CFFEEE
CFFFFC
CFFGEC
DEFFED
DEFGDD
DHDEED

AGCGCC

AADDDD
AADEER
AAEEEA

AADDEC

AIDDDD
AIDEEB

AIDDEC

ABEDDD
ARF EBD
ABFEAC

ABEDEC

ABFEEA

ABFCDD

ABFRDC
ABGCCD

BBDDDD
BBDEEB

BBDDEC

BFHFCC
BFHEEB
BCEDDD
BCFEBD
BEHDDC
BCFBDC
BCGCCD

ACCFBC

BCEDEC
BDEGDB
BFHDDD
BDCEDB
BDHDCC

BCFCDD

BFHDEC

ADDDFA
AFDEFD
ADDEFB
ACEEDD
AEEFFC
ADG EFA
A EGGDB
ADHEEA
ACGCCC
AEFDFD
ADEFFB

ADDGDB
ACFDDD
AFDFFC

AEFGEB
AEEEFD

BFGGCC
BEDDEB
BEFDED
BDEFEE
BEEFBE
BEDEEC
BDFCDC
BDGCCC
BEFFDD

EEDFCB
BFGDFC
BEDEFE

BFGEFB

AECGCC
ACFGEC
AECFFP
AECEFb
ADFFFA

ACDF EA
ACDGCE
ACDGDA
ACEEEC
ACEFCD
ACEFEB
ACEGAA
ACEGCC
ACEGDB
ACFFAC
ACFFBD
ACFFEA
ACFGDA
ACGDCD
ACGGBB
ACGGCA
ACHDCC
ADDFFA
ADECFA
ADEEED
ADEFDD
ADEGBA
ADFCFB
ADFDFC
AOFFCD
ADFGBB
AOGOOD
ADGOFB
ADHCDB
ADHDDC
ADHDEB
AEAEEA
AEEFEA
AEEBFA

ADGGCE
AFFFFA
AEFFFB

AEEGDD

AEf-FDE
AGGGBB
ATFEEP
AHF CCE
ADDGEA

ADEEFC
ADLGDC

AEGEFB
ADFGCC
AEFFCE
AEBEEB
AEGODE

AGCDFC
AFGBFB
AGOGCD

AHEEBE
AHDDDE
AHDEFE

AHDDFC

AEFGAE

AHEEFA
AEEEEE

AEEGEC


AGDFFB

AGGCFE

AFCFFB

AGDDFD

EEDFDC
BDFDDD
BFCEEC
BEEGDC

BEEEED
BEFFCD
BFEEEE

BEEEFC BEFDFC EEFGCC
BEGCDC BFEEFD BFEFFC
BFEGEC

ADEGEB

BEBECC
BEEFFB
EEGDDD
BEFFEC
BFFDFD

BEEGEB
BFEFDE
BFFFFB

BEFCFE
BFEGDD

CCF FCC
CCFDDD

CCFDEC

AGEFFA

AFGCFC
AEFGCD

CDFEDD
CGEEFD
DDFFDD
CFFEFD
EFGEFE
CGEEEE
CEFFDD
CHEDFD
EGEGE E
CHDDED
CHFCEE
CFFGDD
FFFFFF

CDFFCD
CIDDDD
DDGEDD
CIEDFC

CDGDDD
CIEDDE
EGEFFE
DFFFEE

DGEFEE DHEEEE
DGEFFD


DHEEFD

CHEFCE

AEGDFC

CIEECE
CHDDFC

CHEDEE

DEGEED
CIDECD
CGEFFC

DFFFFD
CGEGDD

AHDECE

CICDCD EFFFFE


2T.24

THE FIFTY POLYHEDRA WITH 14 VERTICES.*  HAHXLTON CIRCUITS
  GRACE

5;iST
   I
1.0
2rr
3ro
4eo
5.e
6*.
70.
80.
9*.
10.0
11.0
120.
13.0
140 0
15,.
16.0
??? o
180.
19.r
20.0
21.6
22a*
23ee
24e o
250.
2660
27**
28.a
29e.
30eo
31.e
32.0
33.0
34er
350 0
36*B
31b.
38ae
39eo
404 d
41.0
42me
43.e
44er
45.4
460.
470.
48.e
49be
5044

BDHDGBB
80 I EGDB
BDHFGBD
BEIFDFC
BOFOFDC
CJHECGE
CJGDHFC
CfCOHFD
EKCCCCB
BCCCEBC
BCCUEBB
BCOEBCB
BCCFCEC
BCFCFCB
CHFIGEC
BCCCDBD
BCGDGEC
BDFDF CB
BDGEGEC
BCCEFDB
BC EBEDB
BDJEBDB
80 JCDOB
BCCFFBC
BDECEDB
80 JDECC
BCGHFBC
BEJFDEC
BC IFCFB
BDJDEBB
BCDFBDB
BCCFBEB
BCDFCEB
BFCGDEB
BCDHEBC
BCGDBEB
BDC68DB
BCHCCBB
BDFBECC
BCFGBDC
BCIEBFB
BEHECFB
BDFBEBB
BCFBFBB
BDCEBEB
CKEIECC
BECECEB
BCFBGCB
8CtEGBC
BDHEBFB


2T. 25

YOVP3LYGONAL GRAPHS

VERTICES     VO.

8           1
             RA:l,A:ACA

10

5
   lOA:l,ll:AACA
   1OAllrlO~ABDA
   lOAtl,ll:ABDA
   1OA:lr 10:AEBB
   lOAZl,lO:AECA

12

30
    12Allrl4:AAACA
    12A:1,13tAABDA
    12A:l,l4:AABDA
    12Allrl31AAEAA
    12Atir13rAAEBB
    12A:l,l3rAAECA
    12Allrl4:AAECA
    12A:lr14:ABBCA
    12A:l,l3:ABCDA
    12A:l,13:ABEAB
    12A:1,12tABFBB
    12Allr13rABFBB
    12A:lr 12:ABFCA
    12A:1,131ABFCA
    12A:l,l4:AaFCA
    12A:l,l2tACACA
    12A:1,12!ADADA
    12Allr12:ADREA
    12Allrl3tADBEA
    12A81,14ZADBEA
    12A:l,14:AFDEA
    12A:l,121AGBDB
    12A:1,121AGDDA
    12Allrl2:AGCDB
    12A8lr12:AGEBB
    12A:l,13:AGEBE
    12At1,12:AGECA
    12Allrl38AGECA
    12A:l,13:133EB3
    12ACA:8,8tACA


2T.4 NONPOLYGONAL PLANAR GRAPHS, n = 8, 10, 12.

2T.40


2T.41


2T.42

deleted

Nonpolygonal graphs mapped on Hamilton circuits.

Nonpolygonal graphs for which chemical examples
are known.

N.B.  More detailed figures for some of the above are available in 2T.5.
2T.25 summarizes this list which is purportedly complete.


2T.410

NONPOLYGONAL GRAPHS MAPPED ON HAMILTON CIRCUITS

Q
\ \ \

(8A:1,8:ACA)

(12A:l&:AAACA)

(12A:1,12:AGCDB)

0
I II  \

  /

*
63
\

(12A:l,lhBBCA)

(12A:1,12:AGDDA)

0
/   \

+

   \
6)
\l I

(12A:1,12:ACACA)

(12A:l,lhAECA)

  \
8
\
\

  \
63
\
\ \

(12ACA:8,8:ACA)

(lZA:1,12:AGEBB)

(12A:1,12:AGBDB)

(12A:1,12:AGECA)

(~~A:~,~o:ABDA
Q
I \\ \

0
I \ \
\
\  I

(12A:l,lkABFCA)

(12A:1,13:AAEAA)


2T.411

c&a
I   \

   \
Q

   \
CJ
\\

(12A:1,12:ABFBB)

(12A:1,12:ADBEA)

(12A:1,13:AAEBB)

   \
0
\ \\ t

   \
a
\

@
I   \

(12A:1,13:AAECA)

(12AzlJ2:ABFCA)

(12A:lJbDBEA)

   \
0
' I
\

Q
I   \

(12A:1,13:ADB?ZA)

(12A:1,13:BBEBB)

   \
0
\

   \
@
\
\

   \
0
\

(12A:1,13:AGEBB)

(UA:1,13:ABFBB)

(12A:l,lb:AFDEA)

   \
0
\  \

0
I   \

   \
CB
\
\

(12A:1,13:ABCDA)

(12A:1,13:AGECA)

(12A:1,13:ABFCA)

0
\  I

@
`I
   /

   \
Q
\
\

(12A:1,13:AABDA)

(12A:1,12:ADADA)


CODE

(8A:1,8:ACA)

(12ACA:8,8:ACA)

2T.420

NONPOLYGONAL GRAPHS WITH KNOWN CHEMICAL EXAMPLES

  MAPPING ON
UNDERLYING GRAPH
  .

POLYHEDRAL        CHEMICAL EXAMPLE
FORM             WITH RR1 NO.

6411

7038

  \
@
\ \

(12A:1,14:AAECA)

7044

+3@ -

                    7404

(12A:1,12:AGEBB)  Q


CODE

(12A:1,12:AGECA)

(12A:1,13:AGECA)

(12A:1,12:ABFBB)

(12A:1,12:ABFCA)

  MAPPING ON
UNDERLYING GRAPH

@
\

   \
0
\
\

   \
0

   \
6Y
\

POLYHEDRAL
  FORM

2T.421

CHEMICAL EXAMPLE
WITH &&J NO.

7211

7393

9603

7296


2T.5  FIGURES FOR GRAPHS, n 5 12.

2T.50    n = 0, 2, 4, 6 all forms, and n = 8 polyhedra.

2T.51


2T.52


2T.53


2T.54

  Besides the figures, codes and examples, several
alternative formula representations are given as
illustrations.

n = 8, Planar unions with examples.

n = 10, Polyhedra and planar unions with examples.

n = 12, Polyhedra with examples.

n = 12, Polyhedra and planar unions for which chemical
examples have been found.


GRAPHS OF POLYGONS OF ORDERS 0 - 6

  POLYGONAL
REPRESENTATION

POLYHEDRAL
  FORM

PLANAR MESH
DIAGRAM

SPAN LIST

0

0

0

co

0

11

A

A

w \

2222

O

(>

1313

w

234234

c 0 \
  d

151515


AND POLYHEDRA OF ORDER 8

2T.500

INCIDENCE
MATRIX               CHORD LIST

-                         -

2 3 4
1111
112
   11 3

2 3 4
2    11
12
   2 3

23456
11 --ill

17
17
12

12 41
23 12
34 34

12 41
23 13
34 24

12 45 13

11 2         23 56 25
1      3        34 61 46
   114
     15

23456
2        11
1          12 45 12
  1        2        23 56 34
   2      3        34 61 56
     14
       2 5

EXAMFLE

0

63

I s
( 3
/

RR1 NU?lBER
OF EXAMPLE

292

1754

3620

3618

5262

5256


  POLYGONAL
REPRESENTATION

\
KY?

GAUCHE

`; #

PLANAR MESH
DIAGRAM

SPAN LIST

152244

153153

333333

23635256

e

24642464

3535353s

CUBANE


2T.501

INCIDENCE
MATRIX

23456
2     1 I1

1        2
11 3
   114
     15

23456
2     111

1        2
1    13
   2 4
     15

23456
1 1 111

112
  1    13
    1 4
     1 5

1  I 5
  116
    17

2345678
11        11
  1       12
-7
    11      3
      1        4
       1    15

CHORD LIST              EXAMPLE

12 45 12
23 56 35
34 61 46

12 45 12
23 56 36
34 61 45

12 45 14
23 56 25
34 61 36

12 56 13
23 67 25
34 78 47
45 81 68

12 56 14
23 67 27
34 78 36
45 81 58

I(-
035

NO EXAMPLE                   --

      Hz
&!3

RR1 NUMBER
OF EXAMF'LE

5257

5252

6402


2T.510

  POLYGONAL          POLYHEDRAL
REPRESENTATION           FORM

0

UNIONS OF 8 VERTICES

EXAMPLE

43

RR1 NUMBER
OF EXAMPLE

6452

6381

6400

A

6389

LSP

6399

A

ai@
    5

6415


2T.511

  POLYGONAL
REPRESENTATION

POLYHEDRAL
  FORM

Lk

0

EXAMPLE

83

RR1 NUMBER
OF EXAMPLE

6388

6376

6401


  POLYGONAL
REPRESENTATION

@
Em39

@
CFOEC

TRIVALENT POLYGONS OF 10 VERTICES

POLYHEDRAL
  FORM

EXAMPLE

m

2T.520

RR1 NUMBER
OF EXAMPLE

7036

7033

7034

6550


2T.521

  POLYGONAL
REPRESENTATION

/;=
0 I
RRfG-

I 0 I

POLYHEDRAL
  FORM

0

A

RR1 NUMBER
OF EXAMPLE

9537

6561


2T.522

RR1 NUMBER
OF EXAMPLE

POLYHEDRAL
  FORM

  POLYGONAL
REPRESENTATION

EXAMPLE

2%

7010

A

6852

6999

D

I 0

7026


2T.523

  POLYGONAL
REPRESENTATION

ABEBC

RESEDR

RBFBB

@
\

RBFCR

POLYHEDRAL
  FORM

EXAMPLE

  n-
&

RR1 NUMBER
OF EXAMPLE

6782

7022

7027

7015

7006


27.524

  POLYGONAL
REPRESENTATION

  =z!
@
RCECC .
@
      RECEC

RDRDR

POLYHEDRAL
  FORM

EP

             RR1 NUMBER
EXAMPLE        OF EXAMPLE

7031

7028


2T.525

  POLYGONAL
REPRESENTATION

REBEB

WCEB

RFFBB

POLYHEDRAL
  FORM

4
  \

  -. '

EXAMPLE

RR1 NUMBER
OF EXAMPLE

7021

7020

7042


  POLYGONAL
REPRESENTATION

RGEBB

BBCDB

POLYHEDRAL
  FORM

         2T.526
RRI NUMBER

EXAMPLE        OF EXAMPLE

EEP

7014

6996

6863

7025


TRIVALENT POLYHEDRA OF 12 VERTICES

POLYGONAL GRAPH WITH ISOMORPHS           POLYHEDRAL GRAPH

    Y
Q
BCCCCB

Q
BCCOUB

fii?J
BCDEBB

Q
BCDECC

@
BCOFCB

@
BCFBEB

@
BCFFBC

BFHFOB

Q
BCCEEE

@
BCEBUB

@
BCFCEC

@
BCGDBO

@
BDFBDB

@
BCGCEB

@
BCEFIIB

@
BEHECC

459

@a

7233

r7.530

EXAMPLE


POLYGONAL GRAPH WITH ISOMORPHS

BoErnB          BEGEBC          BFBFCC

BDFOEC

BFBFBB

CGEGEC          CICGCC

CHFCFD          CIFCFC

@
BFCFDC

DtFDFD

POLYHEDRAL GRAPH

#

2T. 531





EXAMPLE

4%

7392


POLYGONS OF 12 VERTICES WITH EXAMPLES

POLYHEDRON             EXAMPLE

        2T.540

RR1 NUMBER
OF EXAMPLE

POLYGON

7233

BCCXIUB

63

7341

BCEBB

7392

/-
\ 0 \

./

7411

0 \

D

7409

7271

\ '
$
&RR

7369

@ \

7120


2T.541

RR1 NUMBER

7358

P QLir
8,,,;8        7407

   Y

7388

7373

7389

7390

7378

7375


2T.542

RR1 NLJMBER
OF EXAMPLE

POLYGON

POLYHEDRON

EXAMPLE

7370

RBHECA

0 /
&A

d 5
  C 0
LO'

7174

7146

9606

0
\

7277

RCHKR

7381

7387

7372


      2T.543

RR1 NUMBER
OF EXAMPLE

POLYGON

POLYHEDRON

EXAMPLE

9558

7230

7276

637

7379

7136

0
' /

7367

RICRCR

7396

RIGBCB

9601

AIGcD6


2T.544

POLYGON

RIGEBB

@
R%CR

Q

66CFCB

Q

BBGCOS

66GEB6

POLYHEDRON

0

EXAMPLE

     J
@

RR1 NUMBER
OF EXAMPLE

7097

7355

9602

9585

7376

7391


POLYHEDRA OF ORDERS 14-24 FOR WHICH CHEMICAL GRAPHS ARE KNOWN

2T.hO

  POLYGONAL             POLYHEDRAL
REPRESENTATION               FORM

             RR1 NUMBER
EXAMPLE        OF EXAM-PLE

1 Lf BDGEGEC

16 BDGEHECB

16 BDGEIGDB

G9

@





\ ti
T

833

7529

7511

7623

7622

9706

18 BCCEJHCCB


2T.61

  POLYGONAL
REPRESENTATION

POLYHEDRAL
  RORM

RR1 NLIMBER
OF EXAMPLE

EXAMPLE

F-
@ /

11505

18 BCEKGBBCB

11506

18 KEKGCBBB

@
   -

7636

18 BCELJCDIIB

CD
i-
  ---

   _-

8%

7653

18 CKIELJHFC

F@

7692

20 BCOGEKIFBC

9725

22 BCCENLCEFC-


2T.62

     POLYGONAL
  REPRESENTATION
. . _

0
29 BEQGBBEGBBEB

POLYHEDRAL
  FORM

EXAMPLE

RR1 NUMBER
OF EXAMPLE

9733

9732


2T.70

CODE

(SlW

($3ACA)

($3BCB)

($~ABcB)

($5ACDR)

QUADRI/TRIVALENT GRAPHS DERIVED FROM TRIVALENT GRAPHS, n 5 8
                     -

GRAPH

co

8

A

8
I I

EXAMPLE

RR1 B

655

2035

2030

8777

8964

3948


2T.71

RR1 w

CODE

($5AEBB)

GRAPH

EXAMPLE

  tf;.
,I..
i    Hr

NC
83
  tJr

5272

($A:5AECA)

4482

w

($B:5AECA)

5273

($~BCCB)

3966

is3
    a
  r'

w

($SCECC)

4615

($$ZAECA)

2029

m
   GYJ,
   /

(SS2CECC)

3418