DIMACS Workshop on Discrete Mathematical Chemistry: Abstracts


Two main lectures of one hour each will be presented by

Professor Kurt Mislow
Princeton University
Chemistry Department
Washington Road, Princeton, NJ 08544, USA

"Molecular Rubber Gloves"

In a powerful metaphor that expresses a strong link betwen non-numerical 
mathematics and chemistry, chiral molecules that enantiomerize exclusively 
along chiral pathways have been classified as euclidean and topological rubber 
gloves. The two classes are illustrated with examples drawn from a wide variety 
of structural types. An analysis is provided of commonalities in structural 
design. The relationship of molecular rubber gloves  to the concept of 
homochirality is discussed.

Dr Gunnar Brinkmann
Universitat Bielefeld, 
Fakultät für Mathematik
Bielefeld, Germany

"Problems in Generating Chemical Structures"

Structure generation has a long history in mathematics and chemistry.   While 
the first complete lists of possible isomers (non-isomorphic graphs) were of 
course produced by hand, since the late sixties also computers have been used 
for this task. In fact structure generation is an example of a field where 
chemists and mathematicians have each been able to contribute to the other's 
discipline. So MOLGEN, the fastest program for the generation of general 
chemical isomers, was developed in the group of A.  Kerber - a mathematician - 
and the first computer approach to generate cubic graphs (graphs where every 
vertex has exactly 3 neighbours) - possibly the most important class of graphs 
in mathematics - was done by the chemist A.T. Balaban.

One of the problems that have to be handled is the rejection of isomorphic 
structures. For this task some standard methods have been developed, that will 
be presented in the first part of the talk.  Of course they can not be 
presented in detail in this short time, so they will be demonstrated at some 
easy examples:  Fullerene generation using the spiral algorithm, the 
enumeration of planar polycyclic hydrocarbons with a given number of pentagons 
and hexagons by adding one face at a time, and the construction of tube-like 
fullerenes by gluing together two caps each containing 6 pentagons.

In the second part of the talk a slight modification of the second  example 
will be discussed - that is: We want to generate planar polycyclic 
hydrocarbons, but give the chemical formula (e.g. C142 H24) and the number of 
pentagons we think that might be included in the structure,
instead of the number of pentagons and hexagons. In this case, the method of 
adding one face at a time sometimes gets extraordinarily slow and a completely 
new way to construct the isomers has to be developed.


Twenty-five minute presentations will be made by the following authors:

Abeledo, Hernan
Department of Operations Research
The George Washington University
Washington, DC, USA


Atkinson, Gary W.
Bell Labs
Holmdel, NJ 07733-3030, USA

"Integral Polyhedra and Maximum Resonant Sets"

A set of disjoint hexagons of a benzenoid system is called resonant if there 
exists a Kekule structure that simultaneously contains three matched edges for 
each hexagon in the set. The Clar number of a benzenoid  is defined as the 
maximum cardinality of a resonant set. 
In this paper, we show that linear programming can be used to compute the Clar 
number. Our  result follows from  establishing first that the constraint 
of the optimization problem is  unimodular.  Extensions of this result to 
similar  problems of benzenoid systems and of planar bipartite graphs are also 

Aringhieri, Roberto
Universita degli Studi di Pisa, Italy

(co-authors:  Hansen, P., Malucelli, F.)

"A Linear Algorithm for the Hyper-Wiener Number of Chemical Trees"

The paper addresses the problem of computing the Hyper-Wiener index for 
molecules in the alkanes family. A new algorithm having linear computational 
complexity is proposed. The algorithm  has optimal complexity, and can be 
extended to the family of all the acyclic molecular structures. Some 
computational results are reported.

Basak, Subhash C.
University of Minnesota
Center for Water and the Environment
Duluth, MN, USA

(co-authors: Gute, Brian D. and Grunwald, Gregory D.)

"Use of Graph Invariants in QSAR in Predictive Toxicology"

Cameron, Kathie
Wilfrid Laurier University
Department of Mathematics
Waterloo, Ontario, Canada

(co-author: Sachs, H.)

"Disjoint Monotone Paths in Simple Regions: Some Combinatorial
Geometry Motivated by a Problem about Benzenoid Hydrocarbons"

A hexangonal animal is a connected plane graph with no cut-vertices in which 
every interior region is a unit hexagon.  A hexangonal animal is the skeleton 
of a benzenoid hydrocarbon if and only if it has a perfect matching.  

Consider a hexangonal animal G drawn in the plane so that some edges are 
veritcal. The perfect matchings in G correspond to sets of pairwise-disjoint 
paths running monotonically down from the peaks (locally highest points of the 
outer face of G) to the valleys (locally lowest 
point of the outer face of G).

Some years ago, Horst Sachs asked whether every such set of paths gave the same 
pairing of peaks with valleys.  I was able to answer this question 
affirmatively.  Curiosly, the solution involves throwing away the graph, and 
only considering a simple polygon in the plane given by 
the boundary the outer face.

Our paper (Combinatorica 14, 1994) looked at the following.  A monotone path 
system (MPS) is a finite set of pairwise-disjoint paths (polygonal arcs) in the 
plane such that every horizontal line intersects each of the paths in at most 
one point.  Consider a simple polygon in the plane which bounds the simple 
polygonal region D.  Let T and B be two finite, disjoint, equicardinal sets of 
points of D.  We gave a good characterization for the existence of a MPS in D 
whose top points are exactly T and whose bottom points are exactly B; an 
algorithm to find such a MPS; and sufficient conditions for any such MPS to 
give the same pairing of T with B.  (The last solved the chemistry problem.) 

I have extended this work to find a maximum cardinality MPS with top points in 
T and bottom points in B.

Caporossi, Gilles
Ecole Polytechnique de Montreal
Montreal, Quebec, Canada

(co-author:  Hansen, P.)

"Using AutoGraphiX to Explore Chemical  Graphs"

AutoGraphiX is a program that aims at finding extremal graphs for a graph 
invariant or a function of invariants under constraints (also formulated as 
equalities or inequalities involving invariants). It is based on the recent 
Variable Neighborhood Search metaheuristic. AutoGraphiX allows (i) finding 
graphs satisfying given constraints, (ii) finding optimal or near optimal 
graphs  for various graph invariants, possibly subject to constraints, (iii) 
finding  critical graphs for various invariants, (iv) refuting conjectures in 
graph theory, (v) suggesting new conjectures or sharpening existing ones and, 
(vi) suggesting a line of proof for various properties. Principles and 
capabilities of AutoGraphiX are discussed and illustrated with examples from 
chemical graph theory.

Chandler, Jerry LR
Krasnow Institute for Advanced Study,
George Mason University
McLean, VA, USA

"Applications of Category Theory to Theoretical Biochemistry"

Category theory was introduced as the mathematical study of natural 
equivalencies by S. Eilenberg and S. Mac Lane in 1945 and is developing as a 
central concept of mathematics (Mac Lane, 1987.)   In view of its close 
association with formal logic and its potential to work with a wide range of 
mathematical structures (groups, graphs, lattices, topological spaces and so 
forth), it is surprising that applications of category theory in chemical 
sciences are rare or perhaps nonexistent.  A. E. Ehresmann and J.-P. 
Vanbremeersch have described a categorical
model of  "Memory Evolutive Systems" which has a mathematical structure 
comparable to the mathematical structure of theoretical biochemistry which is 
described here. 

This paper introduces a theory of biochemistry composed from various 
mathematical structures within a logical "shell" of discrete categories.   The 
recent analytical determination of the complete DNA sequences of several simple 
organisms allows a certain sense of completeness to the mathematical theory, 
albeit without knowledge of all biochemical structures within a living cell.  
Constituents of a biochemical system are represented as an organized hierarchy 
categories.  The categories range in mathematical structure from unitary 
objects to sequences of linearly ordered subgraphs (that is, polymers composed 
from labeled asymmetric psuedographs of monomers) to non-bonded sequences of 
chemical processes.  

A chemical  principle, the conservation of matter, is used to augment the 
categorical structures.    A subset of the chemical table of elements form the 
material basis of the enumerations of biochemical categories.  Historical 
categories, termed a connate set, are used to organize heritable attributes.  
Geometric forms are motivated by quantum mechanics and empirical observations.  

The organization of local biochemical transition functors is expressed in terms 
of a "collaborative conformation" which represent units capable of changing 
specific graphs via one or more distinctive mathematical operation such as 
addition, isomerization or other chemical processes.   Higher forms of 
biochemical organization are composed from classes (or families) of 
collaborative conformations into cyclic communications channels.  Several 
categories of cyclic communication channels are essential to normal biochemical 

Category theory may prove useful for describing the trajectories of discrete 
chemical constituents within high dimensional biochemical systems as well as 
the organized response to external chemicals. 

(Discussions with A. E. Ehresmann, P. Kainen and A. Vogt are gratefully 

Collins, Karen
Wesleyan University
Department of Mathematics
Middletown, CT, USA

"Symmetry Breaking in Graphs"

A labeling of the vertices of a graph G is said to be r-distinguishing, 
provided no automorphism of the graph preserves all of the vertex labels. The 
distinguishing number of a graph G is the minimum r such that G has an 
r-distinguishing labeling. For instance, the distinguishing number of the 
complete graph on t vertices is t.  However, the distinguishing number of the 
cycle, Cn, is 3 if n = 3, 4, 5 and 2 if n >= 6.  I will discuss some 
distinguishing results and the kinds of graphs
that have high and low distinguishing numbers.

Constable, E.C.
University of Basel
Institut fur Anorganische Chemie
Basel, Switzerland

"From Coordination Chemistry to Topological Complexity"

Cvetkovic, Dragos
University of Belgrade

"Characterizing Properties of Some Graph Invariants Related
to Electron Charges in the Huckel Molecular Orbital Theory"

Let G be a graph on n vertices with the adjacency matrix A. We consider cosines 
of angles between vectors of a standard (ortonormal) basis of Rn (n-dimesional 
real vector space) and eigenspaces of A, and call them graph angles. It turns 
out that electron charges from the Huckel molecular orbital theory are sums of 
squares of angles belonging to corresponding
eigenvalues. Much of the work in both mathematical and chemical literature was 
devoted to the study of isospectral graphs, i.e. isospectral molecules. We 
present some theoretical and computational results giving an insight as to what 
extent graphs are characterized when both the eigenvalues and angles are known.

Delgado, Olaf
University of Bielefeld
Bielefeld, Germany

"Fast and Simple Embedding of Planar Graphs"

Programs like CaGe are capable of enumerating various classes of planar graphs 
at high speed. For viewing the results conveniently, algorithms are desirable 
which produce plausible graphical representations of these graphs in real-time. 
We will present two such algorithms, one for spatial representations and one 
for Schlegel diagrams.

Dietz, Andreas
University of Montpellier

(co-authors:  Fiorio, C., Habib, M., Laurenco, C.)

"Representation of Stereochemistry Using Combinatorial Maps"

We propose to use combinatorial maps as a non-geometric computer representation 
of convex polyhedral and polygonal stereogenic entities. This model is simple, 
uniform, and general. It allows to represent any spatial arrangement of atoms 
(stereogenic entities, molecular shapes, etc.).

Universitat Bielefeld
Bielefeld, Germany

"Constructive Molecular Geometry"
Dubois, Jacques-Emile
ITODYS, University Denis Diderot Paris VII,
Paris, France

"DARC Concentric and Ordered Description of Structural Entities:
NEW and HYBRID Strategies for Similarity Expression"

Graph theory has long contributed to the development of chemistry, mainly as an 
enumeration tool, but without modifying the fundamental basis of structural 
organic chemistry, i.e. rings, chains, substituents and functions.  In fact 
with molecules considered as ordered chromatic 
graphs, molecular topology has definitely contributed a new vision and new 
tools to our chemical thinking.  We can cite, among others, a clearer view of 
environments, new substructures, site and shape complementarity, new and 
original searching of chemical files
(hierarchically structured inverted files) and numerous and original similarity
equations.  The integration of these conceptual breakthroughs is already 
leading to combinatorial strategies.

This is based on the fact that complex integration can cope with numerous and 
varied topological facts.  Gradually it becomes clear that one can achieve one 
of two things:

- an independent, in-depth and coherent development of topological   concepts 
for molecular representation and similarity handling   (easier progress with 
open black graphs and spanning trees or rings...), - or, in a hybrid 
integration, the gradual merging of the advantages of  recent topological 
landmarks with the classical practices of organic  chemistry.

>From its inception the molecular polyvision of the DARC topological system 
foresaw justified choices, enabling optimized descriptions of chromatic graphs 
for realistic local and environmental acquisition of molecular information.

A rigid canonical code for intensive documentation (very large files) is 
coherent with the concept of a concentric and labelled description of any 

molecular graph.  Moreover, this basic concept has proven its capacity to deal 
flexibly with the myriad situations encountered in
similarity searches, either for information or correlation.

In this presentation, we will discuss the use of the hierarchical NN relaxation 
labelling of environmental sites of a focus and the "fading" or "adaptation" of 
the focus concept in various applications:  screening retrieval with or without 
ring description, general and semi-equivalence
of sites, competitive searching in clusters, site similarity in hyperstructures 
and specific "substructure-property local pair" methods for property 
prediction.  Even generative ordering rules can be "task-oriented" to derive 
and visualize Structure/Hyperstructure similarity
proximity or better information clustering.

In all these strategies, a better use of topology/property relations yields 
better results when these relations are implemented with an appropriate 
internal correspondence and relevant size and distribution of information in 
experiemental data sets.

Elk, Seymour B.
Elk Technical Associates
New Milford, NJ, USA

"The Graph Theoretical Logic Underlying Chemical Nomenclature.  
Why Eulerian Paths are Better Suited for Aliphatic Compounds vs 
Hamiltonian Paths for Benzenoids"

Because the entities that we desire to span when assigning a canonical name to 
an aliphatic compound is a graph theoretical edge set, the most efficient type 
of nomenclature that can be formulated will involve the concatenation of 
Eulerian paths. On the other hand, when the point set being spanned can be 
reduced to a dual set in which a set of congruent rings may be replaced by 
points, a concatenation of Hamiltonian paths which covers this dual set leads 
to a simplified, as well as chemically more relevant, nomenclature system.  
Because the module in benzenoid systems is geometrically the edge fusion of 
hexagons, a molecule represented by such modules is better "nomenclated" by 
concatenating a minimum number of Hamiltonian paths.

Fajtlowicz, Siemion
University of Houston
Department of Mathematics
Houston, TX, USA

(co-author: Larson, Craig)

"Representation of C 60 and GRAFFITI's Conjectures 
about Stable Fullerenes"

An operation on  trivalent graphs  leads from the truncated cube to 
buckminsterfullerene and C60 is the only  fullerene with disjoint  pentagons 
which can be obtained by this method. The construction and the  proof emphasize 
maximal independent  sets  with two fifths of vertices of trivalent graphs. In 
the case of C60 these sets define the structure of bromofullerene C60Br24.

The construction and characterization is a result of work on  conjectures of 
computer program Graffiti about stable fullerenes.

Fan, Bo Tao
Université Paris 7
Institut de Topologie et de Dynamique des Systèmes, CNRS
Paris, France

(co-authors: Panaye, A., Doucet, J.-P. and Barbu, A.)

"Molecular Graph Handling"

Molecular graph handling join to topological descriptors is now  largely 
applied in automated treatments of chemical information. In the current course 
of development in our laboratory of a computer-aided spectral simulation 
/structural elucidation system, we propose various algorithms as new tools for 
molecular graph treatments. Some examples are presented:

The perception of the SSSR (Smallest Set of Smallest Rings), is directly 
achieved from a connection table thanks to the introduction (for the first time 
to our knowledge) of an elimination technique which significantly accelerates 
the search process. The algorithm also saves
memory space since every stored cycle is an element of the SSSR.

The detection of equivalent sites relies on the concept of MOST (Maximum 
Overlapping Spanning Tree) and MINST(Minimum Not overlapping Spanning Tree). 
Two equivalent sites (at a given N-level) must have identical MINSTs at this 
level. Since no matrix manipulation is invoked, the procedure is fast with low 
storage requirements. Up to now, this algorithm,
suffers no pitfalls, even in most complex cases, and gives complete solutions.

Other examples deal with the concept of relative symmetry, considered either at 
2D or 3D level, and on the recognition of a given 3D pattern thanks to Hopfield 
like neural networks.

Fujita, Mitsutaka
University of Tsukuba
Inst. Materials Science 
Tsukuba 305-8573, Japan

"Electronic Structure of Nanographite"

Finite graphite systems with a nanometer scale, called Nanographite, are 
situated between aromatic molecules and bulk graphite. Nanographite should have 
different electronic structure from both ends because it is composed of 
comparative numbers of edge sites and bulk
sites for sp2 carbon atoms. Edge shape gives the critical effect on the 
electronic state.

We have two typical graphite edges of armchair- and zigzag- shapes.  Performingthe tight binding band calculation for one dimensional graphite ribbons with 
those two edges, we find these graphite ribbons show striking contrast in their 
electronic states.  In particular, the
zigzag ribbon possesses a remarkably sharp peak of density of states (DOS) at 
the Fermi level forming almost flat bands, which do not originate from infinite 
graphite. We call it as the Edge state because the wave functions are mainly 
localized on the zigzag edges.  Since our calculation is based on the Huckel 
approximation, the problem is just reduced to the zero eigenvalue problem of 
the corresponding adjacency matrices. The contribution of the DOS peak gets 
maximum and non-negligible when the ribbon has a few nanometers width.

We also propose the generalization of graphite network in higher dimension, 
named "Hypergraphite", in the sense that the corresponding electronic band 
structure becomes zero-gap semiconductor as well as graphite and if a certain 
surface exists the surface localized state
is constructed in a region of the k space. It is concluded that the 
hypergraphite is the network which is bipartite and odd number coordinated. 
From this point of view, we discuss the electronic structure of some silicide 
Gruber, Bernhard
Technische Universität München
Institut für Organische Chemie und Biochemie
Garching, Germany

"Handling Synthesis Planing in Combinatorial Chemistry
by Group Theory"

The algebra of the s- and r-vectors is an adequate formal tool to describe 
chemical objects in an abstract way. Compounds as well as reactions are 
represented by automorphisms including all constitutional and configurational 
aspects. The stereochemistry of simple organic molecules as well as of 
metallo-organic compounds may be described in a unique way. Ionic bonds, 
covalent bonds, aromatics and electron deficiency compounds can be formally 
described without loss of information. Even reaction types and the flow of 
electrons can be described using this algebra. The biggest benefit of this 
approach is its intrinsic group theoretical structure. This does not bother the
chemist for its use but allows the computer to handle and structure huge 
amounts of chemical data. This is especially important for combinatorial

Usually, classical chemical syntheses from n starting materials require 
sequences of at least n-1 preparation steps including separation and 
purification of the intermediates. A perfect alternative for rapid syntheses of 
large varieties of agrichemically and pharmaceutically
relevant products are one-pot syntheses by multicomponent reactions (MCR). Four 
to seven different types of participants (i. e. different isocyanides, amines, 
etc.) mixed in a reaction vessel undergo the transformation to one molecule. 
Using more than one representative of
each type of starting materials, all possible combinations will lead to a 
molecular library of products formed according to the given reaction scheme. 
This is a good basis for finding compounds with desired properties.

The main efforts are to develop procedures that lead to the optimal compound 
with specific properties, i. e. methods how the optimal compound with best 
effects and least side effects can be found. The design of library syntheses 
and the handling of the results require adequate mathematics and computer 
tools. In order to design molecular libraries containing the seeked compound 
one needs other kinds of information than for classical synthesis planning. How 
many different compounds will the library contain? How similar or different are 
these?  Will the compounds show functional groups in similar spatial 
arrangementss? The basic problem is the management of the flood of information 
which is generated. The combinatorial product space based on MCR approaches 
contains by magnitude more structures than all existing structure databases 
together. Using a combination of two Ugi-four-component reactions (involving 
di-carboxylic acids) the available product space will cover 10 up 14 different 
structures from
500 different starting materials. Such vast numbers of data can not be handled 
by usual database systems. The automated syntheses of these compounds would 
take thousands of years.

Data may not be assigned to single structures but to sets of structures, 
determined by the starting compounds and the resulting reactions. Instead of 
comparing single structures one must compare collections without having the 
individual elements. Individuals can not be obtained by selection from an 

intractable set but by selective generation. Such highly efficient methods 
require a cleverly thought-out representation of the chemical objects compound 
and reaction, as it is given by the algebra of the s- and r-vectors.

Originally designed for describing the stereochemistry of chemical reactions 
via permutational isomerism, the algebra of the s- and r-vectors is useful to 
manage molecular libraries as well. It covers all combinatorial, 
constitutional, stereochemical and topological aspects of combinatorial 
chemistry on a profound mathematical basis.

Guo, Xiaofeng
(On leave from Institute of Mathematics and Physics, Xinjiang University
Wulumuqi Xinjiang 830046, P. R. China)
Department of Mathematics and Computer Science**
Drake University, Des Moines, Iowa 50311-4505

(co-author:  Randic, M.)

"An Efficient Algorithm for Determining Fixed Bonds and
Normal Components in a  Bipartite Molecular Graph"*

Determining fixed bonds and normal components of bipartite molecular graphs is 
closely related to enumeration of Kekule structures, and calculations of 
LM-conjugated circuit polynomials, sextet polynomials, and generalized 
molecular bond orders. Some algorithms for determining fixed bonds and normal 
components of benzenoid hydrocarbons had been reported. In this paper, we will 
consider general bipartite molecular graphs. The concept of
maximal alternating growing subgraphs of a conjugated bipartite molecular graph 
G in two directions starting from a root vertex is introduced.  Some 
interesting properties of maximal alternating growing subgraphs and normal 
bipartite molecular graphs are given. Based on the important properties, we 
establish an efficient algorithm for determining fixed bonds and normal
components of a bipartite molecular graph G. The complexity of the algorithm 
depends on the complexity of another algorithm for finding a Kekule structure 
of G. After a Kekule structure has been given, the complexity of the other 
parts of the algorithm  is O(m) = O(n2), where m and n are the numbers of edges and vertices of G respectively. Particularly , if  G is a planar graph or a 
non-planar bipartite molecular graph with the maximum degree of vertices not 
greater than 3, then  O(m)=O(n). 
* The Project supported by NFSC and CSC
Harmuth, Thomas
Fakultat fur Mathematik
Universitat Bielefeld
Bielefeld, Germany

"The Construction of Cubic Maps with Prescribed Genus and Face Sizes"

In this talk I will present a complete method to generate simple connected 
cubic maps SCC-graphs of a prescribed genus where only some faces are allowed, 
e.g. only pentagons, hexagons and heptagons. 

The method is based on the concept of Petrie paths which cut an SCC-graph into 
up to three pieces. These pieces are called patches. We construct an SCC-graph 
by gluing patches into a Petrie path. The main task is to generate all possible 
patches without generating too many patches that do not fit  into a Petrie 

Hefferlin, Ray
Southern Adventist University
Physics Department
Collegedale, TN, USA

"Property Correlations Among Small Molecules"

It has been stated that triatomic molecules are the "meeting places for 
experiment and theory" [Burden, F.R., "Triatomic Molecules, Meeting Places  for 
Experiment and Theory," J. Mol. Struct. 223, 345-353 (1990)].  This talk shows 
correlations of some properties of neutral acyclic triatomics and  refines  the 
concept of molecular stability.  We define three distinct  kinds of molecular 
stability.  One stability is against atomization.  The relevant measure is heat 
of atomization, but the equilibrium constant [A][B][C]/[ABC] is highly 
correlated with it.  The second kind of stability  is against ionization.  The 
measure is of course the ionizatition potential. The third kind of stability is 
that against excitation.  Molecules with large gaps between their ground states 
and their first excited states will  have low internal entropies and partition 
functions at a given temperature, conpared to molecules with smaller gaps, and 
hence these highly correlated thermodynamic properties are measures of this 
third stab
ility.  Properties  pertinent to different stabilities are poorly correlated.  
We show these high and low correlations in a variety of ways (e.g. correlation 
coefficients and Euclidean distances). 
Huson, Daniel
Program in Applied and Computational Mathematics
Princeton University
Princeton, NJ 08544-1000 USA

"The Combinatorics of Periodic Tilings"

Interest in periodic tilings and patterns goes back a long time and one of the 
oldest known mathematical results is the enumeration of the five Platonic 
solids, which is over 2000 years old. Many results have been obtained since 
then. But only recently, over the past 15 years, has an adequate combinatorial 
approach to the study of periodic tilings been developed, in joint work with 
Andreas Dress, Olaf Delgado Friedrichs (both Bielefeld) and Ludwig Balke 

The main idea is that any given periodic tiling (of a simply connected 
d-manifold) can be described in terms of its "Delaney symbol", which is 
essentially a graph that encodes the symmetry and topology of a given tiling.

We have studied periodic tilings of the Euclidean plane, sphere and hyperbolic 
plane in detail and have solved the "two-dimensional classification problem" by 
developing algorithms for systematically enumerating all possible periodic 
tilings for any given symmetry group up to
any given degree of complexity.

Software based on this work allow the systematic exploration of such periodic 
two-dimensional structures and reveals surprising relationships between the 
symmetry groups of all three geometries.

Current work is aimed at the classification of periodic three-dimensional 
tilings and possible applications to the enumeration of crystal structures.

Hyde, Stephen T.
Applied Mathematics Dept.,
Research School of Physical Sciences,
Australian National University,
Canberra, Australia

"2-d Hyperbolic Nets"

A number of chemically relevant frameworks can be mapped onto the simpler low 
genus three-periodic hyperbolic surfaces, related to the three-periodic minimalsurfaces. The mapping is most evident for low density porous nets, such as 
those of zeolites and related materials. Accordingly, euclidean 
three-dimensional frameworks (such as ball-and-stick models of covalentr 
crystals) can be analysed within a two-dimensional hyperbolic geometric 
setting. That approach emphasises the notion of curvature as an intrinsic 
physical parameter of these nets. Some consequences will be presented, 
including relations between ring sizes and density, coordination sequences and 
stability of novel graphite frameworks.

Kerber, Adalbert
Universitat Bayreuth
Bayreuth, Germany

"Mathematics for Combinatorial Chemistry"

The application of the generator MOLGEN for molecular graphs to problems of 
combinatorial chemistry will be described. It will be shown how libraries of 
molecules can be enumerated and generated in order to simulate experiments of 
mass synthesis in advance an in order to check if molecules with prescribed 
properties can be synthesized this way.

Department of Chemistry
University of Georgia
Athens, GA, USA

"Carbon Networks on Cubic Infinite Periodic Minimal Surfaces"

Polymeric low density allotropes of carbon are predicted to arise from the 
decoration of negative curvature cubic infinite periodic minimal surfaces 
(cubic IPMS's) with networks of trigonal carbon atoms containing hexagons and 
one type of polygon with more than six edges.  The cubic IPMS's of interest are 
the P surface and D surface, respectively, which are adjoint surfaces related 
by a Bonnet transformation with an association parameter of =BC/2. Such cubic 
IPMS's have genus 3 and are thus required by the generalized Euler's theorem to 
have 24 heptagons, 12 octagons, or 8 nonagons in their unit cells. Leapfrog 

 transformations from trigonal carbon networks on cubic IPMS's containing only 
non-hexagonal rings (e.g., the
Klein surface in the case of heptagons or the Dyck surface in the case of 
octagons) provide the minimum number of carbon hexagons required for dilution 
of the carbon non-hexagons so that the isolated non-hexagon rule (INHR) is 
satisfied, i.e., no edges are shared by pairs of non-hexagonal faces.  The 
structures of such cubic IPMS's decorated by trigonal carbon atoms are 
conveniently described by the octants of their unit cells, which are required 
to have three-fold symmetry.  This symmetry requirement forces such carbon 
allotropes with carbon hexagons and heptagons or octagons to have 24k + 8 
hexagons in the unit cell (k integer) and those with carbon hexagons and 
nonagons to have 24 k hexagons in the unit cell.  The cubic IPMS corresponding 
to the primitive cubic lattice (i.e., the P surface) requires the carbon atom 
decoration of each octant to be achiral, i.e., to have planes of symmetry in 
addition to the three-fold axis.  If the carbon atom decoration of each octant 
is chiral (i.e., with only the three-
axis and no plane of symmetry), then a D surface corresponding to the 
face-centered cubic lattice is required.
Klavzar, Sandi
University of Maribor
Department of Mathematics
Maribor, Slovenia

"Applications of Isometric Embeddings to Chemical Graphs"

Graphs that can be isometrically embedded into a hypercube are called partial 
cubes. In other words, graph is a partial cube if its vertices can be labelled 
by binary labels of a fixed length such that the distance between any of its 
vertices is equal to the Hamming distance between the corresponding labels. We 
will first recall some known results from the theory of isometric
embeddings of graphs to be applied in the sequel. 

The starting observation for the use of this concept in chemistry is the 
following: benzenoid systems are partial cubes. From here on, one can obtain 
several results for the benzenoid systems: a simple method for computing the 
Wiener and the Szeged index; finding general expressions for the two indices 
for several classes of benzenoid systems; a linear time algorithm to compute  
the two indices. Another application is related to the Wiener index of
phenylenes. Finally, a generalization of the concept of isometric embeddings to 
the so called l1 graphs will be mentioned. 

Most of the reported results were obtained jointly with Victor Chepoi, Ivan 
Gutman, Wilfried Imrich and Bojan Mohar. The corresponding paper for the 
proceedings is being prepared jointly with Victor Chepoi. 

Malkevitch, J.
York College (CUNY)
Department of Mathematics
Jamaica, NY, USA
"Geometrical and Combinatorial Questions About Fullerenes"

Branko Grunbaum and Theodore Motzkin seem to have been the first to prove that 
there are 3-dimensional, 3-valent convex polyhedra with 12 pentagons and h 
hexagons, that is, fullerenes, for every value of h other than 1. A simpler 
proof than theirs of this result will be given. Furthermore, a variety of 
geometrical and combinatorial questions about fullerenes will be raised.

University of Saskatchewan
Saskatchewan, Canada

"Topological Methods of Molecular Shape Analysis"

Ohlenbusch, Helgo M.,
Worcester Polytechnic Institute (MA)

(co-authors:  Aste, T., Dubertret, B. and Rivier, N.)

"Simulation and Analysis of 2D Disordered Cellular Structures"

We perform extensive simulations of two-dimensional disordered cellular systems 
(random, planar, regular graphs of degree 3).  Some physical or chemical 
examples are fullerenes, carbon nanotubes, foams, soap froth or biological 
tissues.  We explore structures with different properties by randomly 
performing local elementary topological transformations (bond switch, or cell 
disappearance).  We model coalescence of cells and division using combinations 
of these elementary transformations.  We analyze the structures and 
correlations as topological trees rooted on a central cell, and as closed 
shells arranged concentrically around a germ
cell.  Simulation results for the two approaches are compared and the 
parameters that statistically characterize the organization of these patterns 
are discussed.  We verify the relations between these parameters in the 

Pancoska, Petr
University of Illinois at Chicago
Department of Chemistry
Chicago, IL, USA

(co-authors:  Nesetril, J., Janota, V.)

"Spectra, Graphs and Proteins.  Discrete Mathematical Tools 
for Structural Studies of Proteins"

Applications of objects of discrete mathematics for encoding protein 3D 
features that are relevant for interpretation of structurally sensitive 
variations of protein optical spectra will be presented. We will demonstrate 
how the fundamental molecular features of protein molecular structure are 
projected into important mathematical properties of graphs (Eulerian character, 
planarity etc.) that can be used to establish conditions for error checking and 
correction in
spectral analysis methods and to gain insight into the rules of protein 
folding.  In cases when graph representation of the protein structure is still 
too detailed when compared to the structural sensitivity of the spectroscopic 
technique, the invariants of the graphs are generated as useful quantitative 
descriptors of protein structure that match the information content of the
experimental data. The necessary ambiguity in analyses that use these 
invariants (there are many protein structures compatible with given structural 
descriptor) can be quantitatively characterized by enumeration of the 
equivalent structures where the unique mathematical properties of the original 
graphs are again instrumental. Examples of descriptors of secondary structure 
segment topology and descriptors of tertiary fold type for proteins will be 
presented and the methods for reduction of the ambiguity of the information by 
comparison of set
of descriptor compatible structures with the sequence based structural 
predictions will be discussed.

Pisanski, Tomaz
Univerza v Ljubljani 
Ljubljana, Slovenia

(co-authors: Fowler, Patrick, Graovac, A., Zerovnik, J.)

"A Generalized Ring Spiral Algorithm for Generating 
Fullerenes and other Cubic Polyhedra"

The so-called ring spiral algorithm is a convenient means for generating and 
representing certain fullerenes and some other cubic polyhedra.  In 1993 
Manolopoulos and Fowler presented a fullerene on 380 vertices without a spiral. 
 No smaller unspirable fullerene is known.  In the spring of 1997, using 
computer, Gunnar Brinkmann found the smallest cubic polyhedron without a 
spiral.  It has only 18 vertices.  Here we generalize the ring spiral apporach 
in order to get a canonical representation for arbitrary planar cubic 
polyhedra.  Some
other questions are addressed:  for instance possible generalization of this 
method to polyhedra of higher genus and to polyhedra with vertices of arbitrary 
valency.  This is a joint work with Patrick W. Fowler, Ante Graovac, and Janez 

Quinn, C.M.
National University of Ireland
Department of Chemistry

"Group and Graph Theory Perspectives on 
Large Icosahedral Carbon Cages"

Relationships between the geometric arrangements of the vertices of Goldberg 
type 1 and type 2 icosahedral polyhedra will be established, using a group 
theoretic procedure for the decomposition of individual structures into the 
various geometric orbits of the icosahedral point group.  It will be shown that 
the application of this procedure to the problem of the solution of the 
adjacency matrices of these structures leads to a simple general routine for 
the determination of eigenvalues and eigenfunctions.

Quintas, Louis V.
Pace University
Mathematics Department
New York, NY, USA

(co-author: Balinska, K.T.)

"A Reversible Random Graph Process for Graphs
with Bounded Vertex Degree"

A process is described in which a graph G randomly has either an edge deleted 
or an edge added. In this way G is transformed into either one of its subgraphs 
or one of its supergraphs. Continuing in this manner defines a Markov chain 
whose sites are graphs. If this process is restricted to graphs all of whose 
vertices have degree no greater than some fixed constant the
Markov chain becomes a model with the potential for physical applications.  For 
example, for the study of chemical species being transformed through the 
breaking or the creating of bonds. It is also noted that the degree restriction 
makes this model considerably more difficult to analyze than the unrestricted 
case. Problems and results concerning the bounded degree model are presented. 

Randic, Milan
Drake University
Department of Mathematics and Computer Science
Des Moines, Iowa, USA

(co-author: Guo, X., On leave from Institute of Mathemnatics and Physics,  
Xinjiang University, Wulumuqi Xinjiang  830046,  P. R. China )

"Path Matrices"

The path matrix of a graph has been recently introduced [1].   The (i, j) 
element of the path matrix is defined as pk where pk is the path of the length 
that is determined by the distance of the vertices i, j.   Hence,  the elements 
of the path matrix are paths of different length.  In the
next step one selects an invariant of paths to construct the corresponding 
numerical matrix for the graph considered.   We have considered the leading 
eigenvalue of the paths as the elements of the matrix and have investigated  
some properties of such matrices.   In particular we found that the leading 
eigenvalue of the matrix of the leading eigenvalues of path as the elements  of 
the matrix show some regularities.   In the case of acyclic graphs (trees) the 
leading eigenvalue of such matrices represents a better index of molecular 
branching than does the leading eigenvalue of the adjacency matrix considered 
by Lovasz and Pelikan. 

[1]     M. Randic,  D. Plavsic and M. Razinger,  Double Invariants,   MATCH
        35, 243-259 (1997)

Rockmore, Dan
Dartmouth College
Department of Mathematics
Hanover, NH, USA

"Group Transforms for Chemistry"

Generalized Fast Fourier Transforms (FFTs) are  families of algorithms which 
efficiently compute the projections of functions defined on finite or compact 
groups onto group-invariant subspaces.  This includes the example of computing 
the  expansion of a function in terms of an eigenbasis for a Hamiltonian. 
Particular cases of interest  include wreath product groups (symmetry groups  
for non-rigid molecules) and spherical harmonic expansions. In this lecture 
I will survey some of the recent advances in these techniques and indicate 
their relation to computational chemistry.

Rowlinson, Peter
University of Stirling
Department of Computing Science and Mathematics
Scotland, UK

"Star Sets and Star Complements in Finite Graphs"

Let ( be an eigenvalue of the graph G with multiplicity k.  A star set for ( in 
G is a set X of k vertices of G such that ( is not an eigenvalue of the star 
complement G - X.  The paper discusses the construction of connected graphs 
with multiple eigenvalues as extensions of connected star complements.

AMS(MOS) 1991 classification : O5C50. The author is grateful for financial 
support from the Royal Society (grant ref. CG/974/SG).

Sachs, Horst
Technical University of Ilmenau
Institute of Mathematics
Ilmenau, Germany

(Co-author:  John, P.)

"Hexagonal Tilings of the Torus, (3,6)-Cages,and Their Spectra"

A (3,6)-cage is a simple polyhedron all of whose faces are triangles or 
hexagons. The spectrum of a polyhedron P or of a tiling T is the spectrum  of 
the graph corresponding to P or T.

Relations between hexagonal tilings of the torus and (3,6)-cages (and related 
objects), and between their spectra, are discussed.
Shinbrot, T.
Rutgers University
Department of Chemical Engineering
Piscataway, NJ, USA

"Granular Patterns and Granular Coarsening"

A rich variety of patterns have been observed during vertical vibration of 
shallow beds of granular materials.  These patterns are formed at low 
amplitudes of vibration.  At higher amplitudes and in the presence of air, fine 
grains develop heaps which coarsen over time.  In this talk, I present new 
experimental results which indicate that the coarsening scales as a power law 
over time with exponent alpha = -1/3.  The mechanism for the instability 
leading to the heaping is understood to be that air preferentially infiltrates 
into the bed through shallower regions.  As it infiltrates, the air entrains 
grains and so intensifies the thickness contrast of the bed.  I present a model 
for this mechanism and show that the model scales also with the exponent alpha 
= -1/3.

Terrones, Humberto
Instituto de Fisica, UNAM
Materia Condensada
Mexico, D.F., Mexico

(co-author:  Terrones, M.)

"Geometry and Energetics of High Genus Fullerenes and Nanotubes"
The discovery  of fullerenes and carbon nanotubes has shown that graphite is 
very flexible and can  acquire different curvatures.  In the case of 
fullerenes, the presence of pentagonal rings of carbon produce the positive 
Gaussian curvature required for the closure. If heptagonal or bigger carbon 
rings are introduced in a graphitic hexagonal mesh, periodic and quasiperiodic
graphitic architectures can be proposed; these heptagons produce the negative 
Gaussian curvature necessary for the periodicity. In this work, we propose 
stable high genus fullerenes (up to genus 11) and nanotubes (up to genus 21) 
without dangling bonds and no pentagonal rings of carbon (no positive Gaussian 
curvature), possessing only hexagons and heptagons. These high genus structures 
have holes and can be regarded as finite zeolites. The electronic properties of 
these new type of hypothetical graphitic arrangements are calculated obtaining 
an interesting local metallic beahviour at the holes.In addtition, we analyze 
the stability of  high genus vesicles up to genus 21 by minimizing the squared 
mean curvature. An analogy between the graphitic structures and vesicles is 

Valdes-Perez,  Raul E.
Carnegie Mellon University
Computer Science Department
Pittsburgh, PA, USA

(co-author: Zeigarnik, A. V.)

"Computer-Catalyzed Chemistry: All Simplest Reaction Mechanisms 
Consistent with the Evidence"

For a given chemical reaction, one would like to know all the simplest reaction 
mechanisms that are consistent with experimental evidence or other background 
knowledge.  Finding all plausible mechanisms involves (i) searching the 
combinatorially possible multistep mechanisms, and (ii) building on whatever 
prior knowledge is available.

I will describe MECHEM, an interactive software aid for elucidating reaction 
mechanisms.  The interaction style is: the user formulates the problem and 
articulates his prior knowledge in the form of constraints; the program reports 
the simplest mechanisms; the user articulates new constraints, etc. until no 
further objections remain.

Our experience over several years indicates that the density of simple 
mechanisms is surprisingly high, so it is easy to overlook plausible 
alternatives without a comprehensive search.  A Chemist/MECHEM collaboration 
can lead to finding reliable knowledge more quickly.

Vismara, Philippe
Montpellier, France

"An Abstract Representation for Molecular Graphs"

The design of a synthesis strategy in Organic Chemistry rests upon the 
perception of the target molecule, particularly the recognition of cyclic 
parts.  We propose an abstract representation of molecular graph which 
describes the structural relationships between patterns (cycles, carbon
chains,...). This representation is based on a polynomial algorithm that 
computes the set of relevant cycles in the molecular graph.  This set is equal 
to the union of all the minimum cycle bases of the graph. The abstract 
representation is integrated in RESYN, a system for
computer-aided organic synthesis.

Wills, Joerg M.
University of SIEGEN
Department of Mathematics
Siegen, Germany

"Large Sphere Packings, Wulff Shape and Crystal Growth"

Atomic dense packing is a fundamental property of crystals and has been 
investigated for a long time. The structural investigations  consider infinite 
(spacefilling) sphere packings without boundary effects. But all packings in 
real world are finite, and so it is natural to describe  the boundary and hence 
the shape of crystals and quasicrystals via dense sphere packings.

Classical crystallography describes the shapes and growth of crystals by 
various minimum energy principles, but usually without sphere packing 

A new parameter depending packing density, introduced by the author in 1992 and 
further developed by U. Schnell, K. Böröczky Jr., M. Henk and U. Betke, is 
flexible enough to model the Wulff shape of crystals, quasicrystals and  
extremal crystals like whiskers, needles and microclusters.

Zeigarnik, Andrew
Lomonosov Academy of Fine Chemical Technology
Organic Synthesis and Biotechnology
Moscow, Russia

"Graphs and Chemical Reaction Mechanisms"

Chemical reaction mechanisms can be represented as (1) chemical equations; (2) 
bipartite multigraphs; and (3) hypergraphs. Outside of chemistry, the concepts 
of hypercircuit and hypercycle have been found suitable for application in 
computer science, combinatorial optimization, transportation analysis, and 
other fields of science. The precise definition of these
concepts, however, do not seem suitable for some applications in chemistry; 
also, they do not preserve the Euler formula which relates cyclomatic number 
with the numbers of edges, vertices, and components of a graph. I suggest an 
alternative definition of hypercircuit and hypercycle that removes the cited 
drawbacks. I also mention some open problems that are of
interest within the theory of chemical reaction mechanisms.

Zhang, Fuji
Xiamen University
Department of Mathematics
Xiamen, Fujian, P.R. China

(co-author:  Li, H.)

"Ordering the Trees with a Perfect Matching by Their Energies"

Recently we proved two conjuctures of I.Gutman on the tree with a perfect 
matching which has minimum energy.Now the trees with perfect matching having 
large or small energies are further determined.

Zheng, Maolin
Information Systems
Cincinnati, OH, USA

(co-authors:  Hansen, P., Caporossi, G.)

"Enumeration of Fusenes to h=20"


Previous: Program
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on November 2, 1998.