NASA CR
STAR
Interim Report to the

National Aeronautics and Space Administration
Grant NsG 81-60

 

DENDRAL-64
A SYSTEM FOR COMPUTER CONSTRUCTION, ENUMERATION AND NOTATION OF

ORGANIC MOLECULES AS TREE STRUCTURES AND CYCLIC GRAPHS

 

 

 

 

‘Part II. Topology of Cyclic Graphs

 

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 Introduction to the Treatment of Cyclic Compounds in
Organic Chemistry.

2.1 General Introduction to the Treatment of Rings.

2.2 The Trivalent Cyclic Graphs.

2.3 Numbering of Vertices and Edges.

2.4 Quadrivalent Vertices.

2.5 Planar Mesh Representations.

2.6 Further Developments in the Theory of Trivalent Graphs.

2.7 Symmetry Classification; General Systematics of Graphs.

2.8 Coding and Reconstruction of a Hamilton Circuit.

2.9 Algorithm for Finding Hamilton Circuits of a Cyclic
Graph.

2.T Tables,
This part consists mainly of an analysis of cyclic graphs to allow the we. 0O0
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., 2.0/7
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:

o™N N Ss
l.e., | | ( ) 4
NA C

(-6) (-N.5) (-S.C.N.2)

ole OR,

Polycyclic structures such as

55> FH CO 6

STEROID NUCLEUS MORPHINE NUCLEUS NAPHTHALENE BIPHENYL

[4] [5] [2] {1], [1]

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 lO
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 ee OL
classification then depends on the set of branch points, the atoms which are
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 7 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

of, f 2f
of the symmetries of the figures, This is dramatized by the two isomorphic
polygonal representations of the bi-pentagon.

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

Zp Lee
as chorded polygons. “

Cg

WZ ASF

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 Zl KL
detailed rules.

To recapitulate, the linear paths and the vertices connecting them are Zo17/
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

ae MOL
diagram (b)

 

 

 

 

 

 

 

PYRENE
(a) (b) (c) (d)
which is readily recognized as isomorphic to the prism (c) and its formal

graph (d). The isomorphism of (b) with (c) could also be established algo- 2
wD ALE

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 Ze

(The non-separable connections of n trivalent objects)

Each link must terminate in 2 nodes; each node has 3 incident links. Zee

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

oZ- ZR,

Several computer programs have been applied together with substan-
tial mama 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 29
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-
gon, with n/2 chords planted across all the vertices.
(Therefore, graphs with a Hamilton circuit may be
called "polygonal".) This conjecture has been

{1] [2]

attributed to Tait 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 be both reassuring and

more elegant (see 2.5).

The trivalent polyhedra of from 0 to 12 vertices have been calculated in

27. 2S
this way, and various representations of each of these are shown (Fig. 2T.5). °
They have also been checked for n < 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 LI 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. All 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).

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.

kKREK KE

 

*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 1/2) to the value for the retrograde sense. Hence for the

prism the span values are:

 

24 =~,

 

 

 

 
Compound Graphs. Unions of smaller graphs have been developed in two ways.
way

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 oF ZO’
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):

ef. LIL
Do such graphs play any role in chemistry?

CHe oe
[~~ Nn

(a) (b) (c) (d)

In fact, none of the 11,524 rings in the Ring Index is gauche; consequently,
e af. LI
xcept for 6CCC, the gauche graphs have been deleted from the figures in this
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.

at

Figure 2.25c shows 6CCC as an internally chorded tetrahedron. That is,

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 Zr
with the optional drawing of crossed paths in representations set out as alter-

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

Interpretive Coding of Vertex Group Diagrams. Z 27D
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 2 Leo

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 Z2ee/

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 2ee

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 Cy in, on, iC, where Cy and Cy are the component

circuits; n, and n, 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 oe

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:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 1 6
3 f E Cc
3 4
SPAN LIST - 234234 INCIDENCE MATRIX
CHORDLIST - 6BCB 2.3 4 5 6
2 5 1 1 1} 1
1 1 2
1 3
1 144
1 6 115
FACE INCIDENCE (DUAL GRAPH) —- BDE ACDE BDE ABCE ABCD B C D_&E
1 1 Ll{A
1 21 148
1 lye
1]D
FACE LIST, VERTICES - 123 2345 456 1346 1256
FACE LIST, EDGES - abg bedh dei efgi aefh
INTERCHANGE GRAPH - bfgh acgh bdgi cchi dfhi bc dei fig hi
1 1211 a
abgi abef abde cdef 1 1 1 b
1 1 lic
1 1 ifd
1 1 lie
1 1] f
Of these various representations, the span list is brief and , being invariant 2G

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

2 3 3 Y
4
™ oy \
3 3 _ 4 4 —_—_—= 2 2
3 2 & 3

2 4

 

 

 

 

 

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

 

 

 

 

2.97
6 1
5 2
LY

 

Vertex Labels

2.37

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:

 

 

 

 

 

we. FP
6
5/19 7A
8
4 2
3
6BCB

 

Edges
Numbering of Vertices and Edges. Before defining the mapping of paths 2 PE
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:

 

 

 

 

 

 

 

 

 

uy } 6
3 * E c
3 7 SPAN LIST -~ 234234 INCIDENCE MATRIX
CHORDLIST - 6BCB 23 4 5 6
2 5 1 1 1

 

 

 

 

4
e
-
eo
e
WP wne

 

 

FACE INCIDENCE (DUAL GRAPH) - BDE ACDE BDE ABCE ABCD BC DE
1 1 1A
1 1 1i)8B
1 lic
1|D
FACE LIST, VERTICES - 123 2345 456 1346 1256
FACE LIST, EDGES - abg bedh dei efgi aefh
INTERCHANGE GRAPH -—- bfgh acgh bdgi cchi dfhi bc def gihii
1 1 #1 1 a
abgi abef abde cdef 1 i oil b
1 1 lie
1 1 lfd
1 1 lte
1 Lif
Of these various representations, the span list is brief and being invariant eGR
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

2 3 3 4

4 oN vy .

3 3 — & 4 —_ 2 2
3 2 4 3

 

 

 

 

 

2 4

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

 

 

 

 

 

6 1
5 2
NY

Vertex Lahels

2.97

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:

 

 

 

 

 

2.2
6
5/19 7N\1
8
4 2
3
6BCB

 

Edges
Numbering of Vertices and Edges. Before defining the mapping of paths oe

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:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 1 6
3 * E c
3 ‘ SPAN LIST - 234234 INCIDENCE MATRIX
CHORDLIST - 6BCB 23 4 5 6

2 ° 1 1 1} 1
1 1 2
1 3
1 144
5

 

 

FACE INCIDENCE (DUAL GRAPH) - BDE ACDE BDE ABCE ABCD B Cc DE
1 1 ifjA
1 1 1B
1 i1ic
1)D
FACE LIST, VERTICES - 123 2345 456 1346 1256
FACE LIST, EDGES -~ abg bedh dei efgi aefh
INTERCHANGE GRAPH —- bfgh acgh bdgi cchi dfhi bc def gi h i
1 1211 a
abgi abef abde cdef 1 lL ol b
1 1 lle
1 1 iljd
1 1 lie
1 1]f
Of these various representations, the span list is brief and , being invariant ZF

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

 

4 a 2 ~ 3 ~

3 3

 

oad
£
No
No

 

 

 

2 by 3 2 4 3

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

 

 

 

 

a. 57
6 1
5 2
SLY

 

Vertex Labels

2.57

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:

 

 

 

 

 

2.52
6
5 9 7IX1
8
4 2
3
6BCB

 

Edges
With non-polygonal forms the numbering of the united circuits must be 2 SL
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:

  
Quadrivalent Vertices. Some organic molecules of considerable interest
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

 

NZ NA ONLY
ao N, YN, 7

(a) (b) (c)

 

 

 

d

The second (c) has the advantage of adding only one virtual node per 4-valent
center. Quadrivalent centers will therefore be treated as collapsed edges of a
parental trivalent graph. The adjacent edges (abcd) can be divided in three
different ways: ab/cd, ac/bd and ad/bc, 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.

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

1. Avoid a separable graph. Hence Cr) is related to QD and not re -).

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

iN may go into
(a) (b) (ce) (c')

BCDDB BCCCB [GAUCHE]
(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

 

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

2-57
importance of a canonical representation.

 

 

 

 

 

 

 

 

ABC BCDE DEFG ABEF IU
OR OR OR
Au FGHI ACOGHU
(OA3 1O0A4A 10A4B 1OAG6 1OA6

WITH MAPPING OF
BENZOPERYLENE
Reconstruction of planar mesh from Hamilton circuit representations.
ak

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. so
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.
The grouping of chords is quite simple. The assignment of N vs. §& ZH

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 does intersect, it should be added to the 5 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.

2.0
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

Cc S “ey
which takes only a topological deformation to yield

  

 

2 DIL

recognizable as
When the map is a 2-connected union an obvious ambiguity may arise, some chords
intersecting with neither of the remaining sets, This does not impair the con-
struction of a planar mesh. Cc 2. SS

A
could be
A
or or 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.
OG

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

B
of BCCB we have N (N
[s

nN
~
~

(N {s
and superimposing the parentheses and brackets we have a descriptive formula
(1)CI0))
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:

 

t ,  € T
0-2 -1-0-3-2-1-3
on Prk n3

 

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 []; 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.232 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 an
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 2S

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

cube and the dodecahedron are included in our trivalent graphs, Ny» Ng, and n

8

respectively. In 1900, however, Briickner“bonstructed the trivalent polyhedra

20

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

However (and independently of the present studies!) Grace has just published a 2b Bs
dissertation on the computation of the polyhedra through n = 18 (Grace, 1965). This

work faces formidable problems in testing for isomorphism (18! = 10°) -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

fF

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 Bruckner had overlooked.

The polyhedra through n = 18 have been verified to have Hamilton circuits,

as listed by Grace. It should be remarked ~ “~

including the classes Ny? M16? and n

1 18

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,,(Tutte's 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 2 ey

Hamilton circuit at its first incidence on a triangle:

7

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.

‘ it

Ar XN aN

I

ORDER = N ORDER = (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). eo
By induction we may then pass over (n)-rpolviréra 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 polyhedra up to 18 vertices from 1555 down to only 55 cases.

Non-triangle-containing

 

N Total Polyhedra Polyhedra

4 1 0 2.¢6
6 1 0

8 2 1

10 5 1

12 14 2

14 50 5

16 233 12

18 1249 34

Total n< 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. we:

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.

3

The most complex rings, in practice, are related to polyhexacyclic
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 7
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.@.,

 

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).
- 7 OS
The polyhedral representations generally make the set of symmetries ,

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

has 12 equivalents

n 3 rotations

 

(
'
i
T 2 rotations
(
! 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. 2 red,

One approach is to generate the whole symmetric group, sy? 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 10! =
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.709
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 ond
1. Take E as the canonical form from table 2?T.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 1(1)n-1 steps

123...n
234...1

). When the permuted incidence matrix becomes congruent with

 

of rotation of its indices [the permutation cycle ( )] before and after

123..n
n..321

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

reflection, (

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 cam be used as is.

 

 

 

 

 

2  (C)
Example. Consider the prism, BCB (B) 1 3
a. This is readily translated into
— —_— — — 4
123456 plus 13,25 and 46. (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

 

 

«Lbs

co)

[321654]

 

 
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

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 Systematics of Graphs. Composition of graphs from Hamilton

Circuits: 2-connected graphs.

N
N
<

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

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

ag. 729
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 praph. (Fig. 2.23). 6
wa. WE

There is no present compulsion to rigidify the notation for such

complex graphs; one suggestion is implicit in the diagram:

 

(38CGD .IGDI DGE*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
smallest non-Hamiltonian polyhedron; it is known to be the smallest which
is cyclically 3-connected. All candidate graphs n < 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.78c and 2.78d in configurations inconsistent with must-edges in these
figures. 2.78c is Tutte's 46-node graph, already figured at 2.23. The dashed

lines on 2.78d correspond to those on 2.77.

OQ-4

(a) (b)

 

(¢) (4d)
Coding and Reconstruction of Hamilton Circuits 2 ¥Q

Each graph is represented as a Hamilton circuit projected on the boundary
of a regular polygon with n vertices. Joining these n vertices are 7 chords,

since each vertex is trivalent. The locations of these chords are specified by

*
eo characters, integers being replaced by the alphabet to obviate punctuation .

2
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
C Cc B
B B B
6 6B 6BC 6BCB

A il F 6 K 11 P 16 U 21
B 2 G T L 12 Q 1T Vv 22
c 3 H 8 M 13 R 18 W 23
D I 9 N 14 s 19 X 2h
E 5 J 10 0 15 T 20 XY 25
Appendix:

Algorithm for finding Hamilton circuits of a cyclic graph.
2.90
Tais is illustrated for an undirected, trihedral graph but should be
generalized without difficulty in an obvious way. The input is a description
of the connectivity of the graph. The essence of the routine is to build
a table of sets of edges so that just two edges incident on each node appear
in any row of the table. The first node is chosen arbitrarily. Ivs three
incident edges are marked current and open. The circuit-fragment table
is started with three rows by listing the 3 pairwise 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-fragnment 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 l.
be If one matches, a circuit of the graph has been closed.
Scan the circuit-fragment (c.f.) table contrasting the
metched edge with the selected edge. Each c.f. where
neither appears is deleted. If one of the two appears
on ac.f., this is augmented by the trial edge. If both
appear, the c.f. ,.ow stands as is unless a tracing of
the c.f. shows it to be prematurely closed whereupon it

is deleted. Go tol.
Cc. If both match two adjacent faces of the graph have been
closed. The preceding subroutine is revised in an
obvious way to close out both matched edges: those ec. f.
rows are retained which are compatible with the indicated
edge allocations. Go to l.
The process is terminated when the open edge list is vacated. If ZF!
this leaves some nodes unused no Hamilton circuit is possible. Otherwise,
the final closure of circuit-fragments leaves a table of circuits. This
must still be scanned to separate the Hardltonian cireuits from the set
of pairwise disjoint circuits.
Zz
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 46 node non-Hamiltonian graph has been searched 2.73
exhaustively. This required ac. f. table of 12,477 rows consuming 29
seconds of a program on IBM 7090. Searches yielding all the circuits of
other large Hamiltonian graphs required a comparable effort.
This procedure may have some utility for studies on classification, 2 1X
isomorphisms, and symmetries of abstract graphs and other network problems

for which the set of Hamilton circuits is often an advantageous approach.

A compiete description of the computer program is available from the author.
REFERENCES

Tait, P. G., Phil. Mag. (Series 5), 17: 30 (1884).
Tutte, W. T., J. London Math. Soc., 21: 98 (1946). (See also reference 3)
Tute, W. T., Acta Math. (Hung.), 11: 371 (1960).

Bruckner, M: Vielecke und Vielfldche. Teubner, Leipzig, 1900.

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

2T.1

2T.2

2T.3

2T.4

2T.5

2T.6

2T.7

GENERAL TABLES.

Count of cyclic trivalent graphs.

Symbolic listing of cyclic trivalent graphs n < 12
and polyhedra n = 14,

(Deleted)
Nonpolygonal cyclic trivalent graphs n < 12.
Figures for graphs n < 12 with chemical examples.

Figures for polyhedra n > 14 which have chemical
examples.

Quadri-trivalent graphs.
‘uoapeyAtod e jo sadezy JO Aequnu sy} UeY SsaT euOo ST STUL
(S961) @08AD 09 BUTpIOD.oyY :
YA FMetey PpeIsTy] 2
*ya}mMetey umerp sainsty I

*qunod s{y} wory papny{oxe are su10j oatds
“lle satypusts y» [*xepuy Buyy ey worzy satdwexa umouy jo ersues jo JuNOD ay} 21e SJoeyoOPIAG UT sizqumy |

 

 

 

 

 

 

 

 

 

[€] [yt] [0] m1 < 92 <
weet eee
[1] [6] [z], €I 42
[1] [9] (tI) ZI zz
[7] [1Z] : cu) TI 02
[¢] [sz] | [S]64z1 O1 gT
{ot] [97] ! [zliscez 6 91
[11] 7 [sv] ! [€]' 0s 8 oT
7 [4] oc ! loleet po [selicgt ! [e] ot l ZI
: [z] ¢ ; [olet | [oz] Le Iv] ¢ 9 Ot
#1 ! [ole ! [6] o1 ¥Z S 8
re ee “ a :
Zw), 0 0 #1 ¥1 : € 4
r 0 0 0 «1 Z z
' 0 0 0 ¥1 T 0
‘suoyuy aeueTg “(aeueT g-uoN) “(zeue Td) BaipayAtog Ssuyy TeoTweyD S80TI19A
swiog ayonesy suoyug + jo 2zaqunyn
S}]MoIF) UoIT THER INOUI TH S3yNoat) UoaTTUeH GIFM

[sydeizg TeoTweayds umouy Jo e1isUas pur]

 

SHdVa9 INWIVAIYL OIIOAD JO ENNOO

T° L2
2T.2 SYMBOLIC LISTING OF CYCLIC TRIVALENT GRAPHS.

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

2T.20
2T.21
2T.22
2T.23

2T.24

Nonpolygonal Forms:

2T.25

4, 6, 8

10

12 Planar polyhedra and unions

12 Nonplanar forms

14 Polyhedra only (with Grace [1965]

catalog number)

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.
POLYGONAL GRAPHS

 

 

 

 

4 VERTICES
POLYHEDRON
4A BB
PLANAR UNION
4B AA
6 VERTICES
POLYHEDRON
6A BCB
PLANAR UNIONS
6B AAA
6C ABB
6D ACA
GAUCHE GRAPH
6X ccc
8 VERTICES
POLYHEDRA
BA BCCB BDDB
8B CECC
PLANAR UNIONS
8C AAAA
8D AABB
BE AACA
8F ABCB
8G ABDA
8H ACDB
81 ADDA
8J AEBB
8K AECA
BL BBBB
GAUCHE GRAPHS
ACCC
BOCC
CDDC DDDD

2T.20
POLYHEDRA
BCCCB
BCDDB
BDEBB
BDECC
CFDEC

BEFDB
BCEEC

PLANAR UNTONS

AAAAA
AAABB
AAACA
AABCB
AABDA
AACDB
AADDA
AAEAA
AAEBB
AAECA
ABBBB
ABBCA
ABCCB
ABCDA
ABDDB
ABEAB
ABEDA
ABFBS

ABEBC

GAUCHE GRAPHS

AACCC
ABDCC
ACCEA
ACODC
ACDEB
ACEEA
ADECD
ADFCC
AGCCC
BBCCC
BCDCC
BDCDB
BDDDC
BDODEB
CCECC
CDEDC
CEEDD
CEEEC

ADDDD
ADEEB
AEEEA

BEFCC

BEEES
BEDCD

DFDED
CFDDD
CGCccc

ADDEC

BEDEC

cGbcD
EEEEE

10

VERTEX

GRAPHS

 

DEEED

ABFCA
ACACA
ACECC
ACFCB
ACFDA
ADADA
ADBEA
AEBEB
AFCEB
AFDEA
AFFBB
AGBCB
AGCDB
AGOCA
AGEBB
AGECA
BBBCB
BBCDB
BBEBB

AECEC
ADF DB

2T.21
POL YHEDRA
BCCCCB
BCCDDB
BCDEBB
BCDECC
BCDFCB
BCFBEB
BCFFBC
BDECDB
BOFCEB
BDFDEC
BOGDEB
BFBFBB
CGEGEC
CHFCFD

BFHFDB
BCCEBC
BCEBDB
BCFCEC
BCGDBD
BOFBOB
BCGCEB
BEGEBC
BDGEBD
BEGECD

CICCCC
CIFCFC

PLANAR UNIONS

AAAAAA
AAAABB
AAAACA
AAABCB
AAABDA
AAACOB
AAADDA
AAAEAA
AAAEBB
AAAECA
AABBBB
AABBCA
AABCCB
AABCDA
AABDDB
AABEAB
AABEDA
AABFAA
AABFBB
AABFCA
AACACA
AACECC
AACFBA
AACFCB
AACFOA
AADADA
AADBEA
AADFAA
AAEBEB
AAEFAB
AAEFBC
AAEFDA
AAFFAA
AAFFBB
AAFFCA
AAGABB
AAGACA
AAGBCB
AAGBDA
AAGCDB
AAGDDA
AAGEAA
AAGEBB
AAGECA
ABBABB
ABBACA

AABEBC

AAECEC

AADFDB

 

12. VERTEX GRAPHS

BCEFDB

BEBEDSB

BEHECC

BDHDDB

BFBFCC

BFCFDC

DHFOFD

ABBBCB ACADDA
ABBBDA ACAEBB
ABBCDB ABBDBC ACAECA
ABBDAB ACEBDA
ABBDDA ACECEA
ABBEBB ACFBOB
ABBECA ACFCEB
ABCBCA

ABCCCB

ABCCDA ACFDEC
ABCDO0DB ABCEBC ACGBBC
ABCEAB ACGBDA
ABCEDA ACGCEA
ASCF8B ACGDEB
ABCFCA ACGEAC
ABDACA ACHBAB
ABDEBB ACHBCA
ABDECC ABFCEC acHcce
ABDFBA ACHCDA
ABDFCB ABGDBD = ACHDAA
ABDFDA ABGDAC ACHODDS
ABEADA ACHEBC
ABEBEA ACHEDA
ABEEAB ACHFBB
ABEFAA ACHFCA
ABEFDB ABGBCC ADADDB
ABFADB ADAEDA
ABFBEB ADAFBB
ABFFAB ABGBEA AD8G8B
ABFFBC ABGCEB ADGADA
ABFFDA AOGECD
A8GBBB ADHABB
ABGCAB ADHEBB
ABGDEA ADHECC
ABGFBB ADHFDA
ASGFCA AEAFCB
ABHBCB AEBGCB
ABHBDA AEGAEA
ABHCAA AFAFAA
ABHCDB ABHDBC AFAFOB
ABHDAB AG8GBC
ABHDDA AGEGEA
ABHEBS AHBDEB
ABHECA AHBEEA
ACAACA AHBGBB
ACACDB ACAOBC AHCGCB

ACGEBD
AECGDB
AGEBFC
AGECFD
ADBEDB
ADBFDA
ACGEEA
AGDGEB
AECGEA

AHF DBE
AHFDFA

AHFCFB
ADHFCB

AHECFC

AGOBFB

AHEBFB

AHOGOB
AHEAEB
AHEGDA
AHF AEA
AHF GBB
AHHBCB
AHHCDB
AHHDOA
AHHEBB
AIBBBB
AIBBCA
AIBCCB
ATBDDB
AIBEDA
AIBFBB
AIBFCA
AICACA
AICECC
AICFCB
AIDADA
AIDBEA
AITOFAA
ATEBEB
ATEFBC
AIEFDA
AIFFBB
AIFFCA
AIGBCB
AIGCOB
AIGODA
AIGEBB
AIGECA
BBBBEB
BBBCCB
BBBDOB
BBBFBB
BSCECC
BBCFCB
BBEBEB
BBEFSC
BBFFBB
BBGBCB
BBGCOB
BBGEBB
BCBBCB
BCBCDB
BCHCDB

2T.,22

AHEGBC

ATBEBC

ATECEC
ATOFDB

BBBEBC

BBECEC
BBDOF DB

BCHDBC
AAACCCE
AABDCC

AACCEA
AACDOC
AACDEB
AACFEA
AANECD
AADFCC
AAGCCCE
ABBCCC
ABCDCC
ABDCOB
ABDCEA
ABDODC
ABDDEB
ABDEEA
ARBEECD
ABEEER
ABEFCC
ABFACC
ABHCCC
ACACCE
ACCDDA
ACCECC
ACCEDR
ACCFDA
ACCGBB
ACCGCA
ACDDEA
ACDEDC
ACDEEB
ACDFCC

ACDFEA
ACDGCB
ACDGDA
ACEEEC
ACEFCD
ACEFEB
ACEGAA
ACEGCC
ACEGDB
ACFFAC
ACFFBD
ACFFEA
ACFGDA
AGGDCD
ACGGBB
ACGGCA
ACHDCC
ADDFFA
ADECFA
ADEEED
ADEFDO
ADEGBA
AOFCFB
ADFOFC
ADFFCD
AOFGBB
AOGOOD
ADGOFB
ADHCDB
ADHDDC
ADHDEB
AEAEEA
AEBFEA
AEEBFA

AADDDD
AADEEB
AAEEEA

ABEDDD
ABFEBD
ABFEAC

ABFBDC
ABGCCD

ACCFBC

ADDDFA
AFDEFD
ADDEFB
ACEEDD
AEEFFC
ADGEFA
AEGGDB
ADHEEA
ACGCCE
AEFDFD
ADEFFB

AEGCGCC
ACFGBC
AECFFA
AECEFB
ADFFFA

AEPFDE
AGGGBB
ATEEEA
AHF CCE
ADDGEA

ADEEFC
ADEGDC

AEGEFB
AOFGCC
AEFFCE
AEBEER
AEGODE

AHEEBE
AHDDDE
AHOEFB

AEFGAB

AADDEC

ABEDEC

ABFEEA

ADDGDB
ACFODD
AFDFFC

AHEEFA
AEEEEE
ADEGEB
ADGGCB

AFFFFA
AEFFFB

AEEGDD

AGEFFA

AFGCFC
AEFGCD

AGCDFC
AFGBFB
AGOGCO

AHDDFC

 

12. VERTEX GAUCHE GRAPHS
AEFBFB
AEGECE AGCGCC
AFAFCC
AFCEFC
AFGEFA
AGCCFB
AHCOFB
AHOGCC
AHECDE
AHHCCC
AIBOCC
AICDDC AIDDDD AIODEC
AICOEB AIDEEB
ABFCDD AIDECD
AIDFCC
AIGccc
BBBOCC
BBCDDC BBODDD BBDDEC
BBCDEB BBOEEB
BBDECD
BBDFCC
BBGCCC
BCBCCC
BCCDCC BFHFCC
BCDCDB BFHEEB
BCDDDC BCEDDD BCEDEC
BCODEB BCFEBD BDEGDB
BCEECD ®S8EHDDC BFHDDD
BCEEEB BCFRDC BDCEDB
BCEFCC BCGCCD BODHDCC
AEFGEB BCHCCC
AEEEFD BOCECC BFGGCC
BODCDB BEDDEB BEDFCB
BDDEDC BEFDED BFGDFC
BODEEB BDEFEB BEDEFB
BDDFBB BEEFBB
AEEGEC BDOFCC BEDEEC BEDFDC
BDEEDD BDFCDC BDFDDD
AGDFFB BOEEEC BDGCCC BFCEEC
BDEFCD BEEFDD BEEGDC
BDEGCC
AGGCFB BOFBCC BEBECC
BOFFBD BEEFFR BEEGEB
AFCFFB BOGOCD BEGODD BFEFDE
BEECEB BEFFBC BFFFFB
BEFCEC BFFDFD
AGDDFD BFFBFB
eeccee
ccDDCC §=CCFFCC
CCEDDC CCFDDD CCFDEC
CCEECC
CDEEDC CDFEDD CDFFCD
COFEEC CGEEFD CICODD
AEGDFC CDGCDC DDFFDD ODGEDD
COGDEC CFFEFD CIEDFC
CDHDCD EFGEFE
CEEFEC CGEEEE CIEECE
CEFEED CEFFDD CHDDFC
CEFEFC CHEDFD
CEGCEC EGEGEE
CEGDED CHODED DEGEED
CFFEEE CHFCEE CIDECD
AHDECE CFFFFC CFFGDO CGEFFC
CFFGEC FFFFFE
DEFFED
DEFGOD
DHDEED

2T.23

BCFCDD

BFGEFB

BEEEED
BEFFCD
BFEEEE

BEFCFB
BFEGOD

COGDDD
CIEODE
EGEFFE
DFFFEE

CHEDEE

DFFFFD
CGEGDD

BFHDEC

BEEEFC
BEGCDC
BFEGEC

OGEFEE
DGEFFD
DHEEFO

CHEFCE

circoco

BEFOFC BEFGCC
BFEEFD BFEFFC

OHEEEE

EFFFFE
THE FIFTY POLYHEORA WITH 14 VERTICESes

GRACE
LIST
NOs
les
Zee
Bee
hee
See
bee
Tee
Bees
Yee
lOee
llee
l2e6
l3eec
L4ee
15e.6
l6e6
l7es
180s
19 ¢.6
2000
Z2lee
2260
2300
24e6
25 ee
26060
2Teoe
2Be6e
29 e0
3000
Blee
32e0
33060
Shee
35e6
3608
3Tee
38e0
39 ee
4Oee
4les
42e0
4300
Shes
45e6
46e0
S&T ee
48e6
49 a6
50es

BOHDGBB
BOTEGOB
BOHF GBD
BEIFDFC
BOFDFOC
CJHECGE
CJGDHFC
CIGDHFD
BCCCCCB
BCCCEBC
BCCDEBB
BCOEBCB
BCCFCEC
BCFCFCB
CHF IGEC
BCCGDBD
BCGDGEC
BOFOFCB
BOGEGEC
BCCEFDB
BCEBEDB
BOJEBOB
BOJCDOB
BCCFFBC
BOECEDB
BD YDECC
BCGHFBC
BEJFDEC
BCIFCFB
BOJDEBB
BCDFBDB
BCCFBEB
BCOFCEB
BFCGDEB
BCOHEBC
BCGOBEB
BOGBBDB
BCHCGBB
BOFBECC
BCFGBOC
BCTEBFB
BEHECFB
BOFBEBB
BCFBFBB
BOGEBEB
CKEITECC
BEGECEB
BCFBGCB
BCTEGBC
BOHEBFB

HAMILTON CIRCUITS

2T.24
VERTICES

8

10

12

NONPOLYGONAL GRAPHS

NO.

1

30

BAt1»BSACA

LOAT1s,112AACA
1OAt1s103ABDA
LOAt1,112ABDA
1OAt1+103AEBB
1OAS1,102AECA

12At1Ls 142 AAACA
12At1»+13%3AABDA
12A31s1423AABDA
L2Ati, 133 AAEAA
L2ASi,138AAEBB
LOAtLsLIsAAECA
12AS1e148AAECA
12A%1»+1423ABRBCA
12Atis1l32:ABCDA
L2At1+ 1323 ABEAB
Y2A%1i»+ 12: ABFBB
12Atts132ABFBB
12A% is 12sABFCA
L2A%l»sl132ABFCA
L2A%1+142ABFCA
L2AL tr» 122ACACA
L2At Ts» L2zADADA
LV2At1,12°ADBEA
L2Atis1L3tADBEA
L2At1L» 142 ADBEA
L2ASLs 14:2 AFDEA
12As1is122AGB0B
L2Atis 122AGDDA
12A%1,122AGCD8
12Az1s12°:AGEBB
12A%1s13:AGE8B
L2At1» 12° AGECA
L2A%t,138AGECA
12A%1.13:88EB8
L2ACAS Bs B82 ACA

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

2T.40 deleted
2T.41 Nonpolygonal graphs mapped on Hamilton circuits.
2T.42 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.
NONPOLYGONAL GRAPHS MAPPED ON HAMILTON CIRCUITS

a

an
is
HH
oo
‘>
Q
tS

, 8: ACA)

(10A:1,11: AACA)

2

(10A:1,10: AEBB)

2

(10A:1,10:AECA)

oD

(10A:1,10:ABDA)

o

(10A:1,11:ABDA)

(12A:1,14:AAACA)

J

on Ss

(12A:1,14:ABBCA)

(12A:1,12:ACACA)

2
©

(12ACA: 8,8: ACA)

CQ
Y,

(12A:1,12: AGBDB)

D

(12A:1,14:ABFCA)

2T.410

7,

(12A:1,12: AGCDB)
QD

(12A:1,12:AGDDA)

(12A:1,14: AAECA)

(12A:1,12:AGEBB)

(12A:1,12:AGECA)

(12A:1,13: AAEAA)
oO

(12A:1,13:AAEBB)

a
od

(12A:1,23:AAECA)

oO
QO

(12A:1,13:BBEBB)

C
e

(12A:1,13: AGEBB)

DL

(12A:1,13:AGECA)

CQ)
0

(12A:1,13: AABDA)

oD

(12A:1,12: ABFBB)

(12A:1,12: ABFCA)

(124:1,14:AABDA)

(12A:1,13: ABFBB)

\

(12A:1,13:ABFCA)

(12A:1,12: ADADA)

2T.411

tO

(12A:1,12: ADBEA)

(12A:1,14:ADBEA)

(12A:1,13: ADBEA)

 

 

(12A:1,13: ABEAB)
(8A:1,8: ACA)

(10A:1,10: AECA)

(10A:1,10:ABDA)

(12ACA:8,8:ACA)

(12A:1,14: AAECA)

(12A:1,12: AGEBB)

2T.420

NONPOLYGONAL GRAPHS WITH KNOWN CHEMICAL EXAMPLES

MAPPING ON
UNDERLYING GRAPH.

\

QOBDE

 

POLYHEDRAL CHEMICAL EXAMPLE
FORM WITH RRI NO.
6411

7213

7119
CODE

(12A:1,12: AGECA)

(12A:1,13:AGECA)

(12A:1,12:ABFBB)

(12A:1,12:ABFCA)

MAPPING ON

UNDERLYING GRAPH

2OO@D

POLYHEDRAL
FORM

2T.421

CHEMICAL EXAMPLE
WITH RRI_NO,

Cao

7211

cogeoo

7393

ols

9603

7296
2T.5

FIGURES FOR GRAPHS, n < 12.

2T.50

2T.51

2T.52

2T.53

27.54

n= 0, 2, 4, 6 all forms, and n = 8

Besides the figures, codes and
alternative formula representations
illustrations.

n = 8, Planar unions with examples.
n = 10, Polyhedra and planar unions
n = 12, Polyhedra with examples.

n = 12, Polyhedra and planar unions

examples have been found.

polyhedra.

examples, several
are given as

with examples.

for which chemical
POLYGONAL

REPRESENTATION

 

 

 

 

BB

 

 

 

 

AR

 

 

 

 

 

BOB

ARA

POLYHEDRAL
FORM

CO

GRAPHS OF POLYGONS OF ORDERS 0 - 6

PLANAR MESH

DIAGRAM

 

0
AN
00
iz
ey

SPAN LIST

11

2222

1313

234234

151515
AND POLYHEDRA OF ORDER 8

 

INCIDENCE
MATRIX

N
iw
+

 

-
pe

 

a
Wo hr

 

 

nN
w
oS
uw
oy

 

e
mem ee
re

l

 

Mm FWN

Wf wh re

CHORD LIST

1?
1?
12

12 41
23. 12
34 34

12 41
23 13

34 24

12. 45
23 56
34 61

12. 45
23 56
34 61

13
25
46

12
34
56

EXAMPLE

CO

2T.500

NUMBER

OF EXAMPLE

292

1754

3620

3618

5262

5256
POLYGONAL POLYHEDRAL
REPRESENTATION FORM

\ ©

ABB

WY

RCA

CLUDD

GAUCHE

COC

 

 

 

 

 

 

 

 

PLANAR MESH

DIAGRAM SPAN LIST

152244

153153

333333

23635256

24642464

 

35353535

 

 

 

CUBANE
INCIDENCE
MATRIX

~
ry
Wf Wh Fe

wy
ro
UP ONE

 

I fF WM Fe

 

 

SOW PWN

NOuPwnr

CHORD LIST

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

EXAMPLE

2,

NO EXAMPLE

oor

 

2T.501

RRI NUMBER

OF_EXAMPLE

5257

5252

6402
2T.510
UNIONS OF 8 VERTICES

POLYGONAL POLYHEDRAL RRI NUMBER
REPRESENTATION FORM EXAMPLE OF EXAMPLE
ee

C} 7: 6452
Sy

RAAA

©) LB

ABB

RAGA

—

QO DB #2 -«
ABCB

Q Kk «&

mM

REOR

ss

S) 5B bY 388
AGE

ADA
POLYGONAL

REPRESENTATION

iO WZ) Dd

POLYHEDRAL
FORM

&
Qo
=

EXAMPLE

2T.511

RRI NUMBER

OF EXAMPLE

6388

6376

6401
TRIVALENT POLYGONS OF 10 VERTICES

POLYGONAL POLYHEDRAL
REPRESENTATION FORM
“—
BCCCS
BEFOB
BCDB
BCEBC

oe

BDEBB

 

 

 

 

SS 1D

CFOEC

EXAMPLE

oo

a.

2T.520

RRI NUMBER

OF EXAMPLE

7036

7033

7034

6550
POLYGONAL

REPRESENTATION

—s
ele

#

er
ARARA

=

ARABB

ARACR

Aid
7K PA ORO

RRBDA

RACOB

RADDA

POLYHEDRAL
FORM

EXAMPLE

R~(O-R

@ 4
oa

R= -(CH20CH2)a~

He—+H2
Ha SOW
ae \
48 “]
A

a ae

2T,521

RRI NUMBER

OF EXAMPLE

9537

6561
POLYGONAL POLYHEDRAL
REPRESENTATION FORM

—y
=

“~—
RRERA

RREBB

ARECR

ABBBB

>

ABBR

=

ABCCB

So vreodps sz

ABCDR

EXAMPLE

2T.522

RRI NUMBER

OF EXAMPLE

7010

6852

6999

7026
POLYGONAL POLYHEDRAL
REPRESENTATION FORM
TS
=
ABDDB

D)

ABEBC

a/
WD

/

i

ABEDA

ABF BB

gf

A@BFCR

Sy

Q
Qe EA B®

ACRCR

EXAMPLE

2T.523

RRI NUMBER

OF EXAMPLE

6782

7022

7023

7015

7906
27.524

POLYGONAL POLYHEDRAL RRI NUMBER
REPRESENTATION FORM EXAMPLE OF EXAMPLE

—al
=

 

 

RCECE

 

 

 

 

RECEC

7031
a cose

RDF DB

X L& ty 7028
ACFDA
a
fo
RDADA

ADBEAR
2T.525

POLYGONAL POLYHEDRAL RRI NUMBER
REPRESENTATION FORM EXAMPLE OF EXAMPLE

/

AFFBB

EQ om
Bh

/

7042

i

DB
3
2
POLYGONAL

REPRESENTATION

RGEBB

O

BBBCB

©

BBUDB

z
iY

POLYHEDRAL
FORM

CLLEOOD

EXAMPLE

wo

2T.526
RRI NUMBER

OF EXAMPLE

7014

6996

6863

7025
TRIVALENT POLYHEDRA OF Je VERTICES €T.5350

POLYGONAL GRAPH WITH ISOMORPHS POLYHEDRAL GRAPH EXAMPLE

oO
oS

BCCCCB

©
OQ
©

Y
628 ee @

BCCDOB

©
(OD

BCDEBB

©
©

BCDECC

Bie
P

BCF REB

QD
D

BOF FBC

BFHFDB

BCCEBC

BCEBDB

BOF CEC

D

BCGDBD

BOF BDB

BCGCEB

 

BCEFDB 7233
a
Ene
BEBEDB 7341

BEHECC

BOHODS
eT. 53

POLYGONAL GRAPH WITH ISOMORPHS POLYHEDRAL GRAPH EXAMPLE
BOECOB BEGEBC BFEFCC

BOF CEB BOGEBD

 

BOFOEC BEGECD BFCFDG

BDGDEB

SO

BFEFEB

eS

QO

CGEGEC CICCCG

Oo

CHF CFD CIFCFC DHF DFD

7392

QD
mw 8 ek @ SB @

eS
POLYGON

 

©)

BCCOOB

©

BCGEBB

GGEGEC

PRBBEB

RAGEBB

POLYGONS OF 12 VERTICES WITH EXAMPLES

POLYHEDRON

EXAMPLE

OO
5B
oP

4
&

OH,

9
;

‘

2

VP
b

» EB &

RRI NUMBER

OF EXAMPLE

7233

7341

7392

7411

7409

7271

7369

7120

2T.540
2T.541

RRI NUMBER
POLYGON POLYHEDRON EXAMPLE OF EXAMPLE
GQ) coca 7358
\
BAGECA
= oA Nan
QO @ &s -
PEBRBB
) LB om es
ABCFBB
(J cB»
ABCFCA
S « # -
REDFBA
© So «& -
ABEFGB
© 5 4 : 7378
ABHEOR
SOS 2 & »

/

ABHOR
2T.542

RRI NUMBER
POLYGON POLYHEDRON EXAMPLE OF EXAMPLE
=
eee
YX Q IS
ABHECA
= ON ean
oy we IO 7174
f Co aN) N*
— No” 7
RCARCR
OF
care 7146
\ f
ACRECR
CO Bm
RCGEBC
oO
ACHBCA |
é
S 7381
AGHOAR
Se BO 7387
a )
ACHFEE :
ges
coy? m

 
POLYGON

 

POLYHEDRON

ABwWRPEARHA

EXAMPLE

So

BS & f bd B

2T.543
RRI NUMBER

OF EXAMPLE

9558

7230

7276

7379

7136

7367

7396

9601
POLYGON

POLYHEDRON

COUUS

EXAMPLE

> b BB

2T.544

RRI NUMBER

OF EXAMPLE

7097

7355

9602

9585

7376

7391
POLYHEDRA OF ORDERS 14~24 FOR WHICH CHEMICAL GRAPHS ARE KNOWN 2T.60

POLYGONAL POLYHEDRAL RRI NUMBER
REPRESENTATION FORM EXAMPLE OF EXAMPLE

9652

OC)

 

14 BCCEFOB

7529

CL

BO)
De ® © ® BQ

14 BOGBBDB

7511

se

 

14 BDOGEGEC

16 BDOGEHECB

7622

&

16 BOGEIGDB

9706

OO
BS
Sm
mo"
So
oe

SE

18 BOCEJHOCB
POLYGONAL
REPRESENTATION

W

18 BCEKGBBCB

WZ

18 BCEKGCBBB

Y

18 BCELJCDOB

&

18 CKIELJHFC

o
Se

20 BCDGEKIFBC

Z

22 BCCENLCEFC”

POLYHEDRAL
FORM

 

ODS
ry

2T.61

RRI NUMBER
EXAMPLE ===——OF_ EXAMPLE

11505

11506

7636

b &

7653

7692

9725

» 8 &
POLYGONAL
REPRESENTATION

5

24 BEQGBBEGBBEB

24 CUCDODGEHECD

POLYHEDRAL
FORM

CY

Oy

—L>

a

EXAMPLE

2T.62

RRI NUMBER

OF EXAMPLE

9733

9732
CODE

($1AA)

($3ACA)

($3BCB)

(S5AACA)

($5ABCB)

(S5ACDB)

2T.70

QUADRI/TRIVALENT GRAPHS DERIVED FROM TRIVALENT GRAPHS, n < 8

 

GRAPH

5

Do 6 Oe

EXAMPLE RRI #
oN ae

| 655
Wn Hy

Ba 2035

Hop
Ha Su

wh

Hi

2030

We
oN

I

Ls 8777

CltE

NL

m4 2

8964

 

“a
H
es 3948
CODE

(S5AEBB)

($A: 5AECA)

(SB: 5AECA)

($SBCCB)

($5CECC)

($$2AECA)

($$2CECC)

GRAPH

 

 

 

 

 

ue

Hs

oO

 

o— the
oa

Coe

2T.71

RRI #

5272

4482

5273

3966

4615

2029

3418