DIMACS Workshop on Discrete Mathematical Chemistry: Abstracts
MAIN LECTURES
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.
COMMUNICATIONS
Twenty-five minute presentations will be made by the following authors:
Abeledo, Hernan
Department of Operations Research
The George Washington University
Washington, DC, USA
and
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
matrix
of the optimization problem is unimodular. Extensions of this result to
similar problems of benzenoid systems and of planar bipartite graphs are also
presented.
-------------------------------------------------------------------------
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
of
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
function.
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
acknowledged.)
-------------------------------------------------------------------------
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
Yusgolavia
"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
Mathematik
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
France
(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.).
-------------------------------------------------------------------------
Dress,Andreas
Universitat Bielefeld
Mathematik
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
materials.
-------------------------------------------------------------------------
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
chemistry.
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
path.
-------------------------------------------------------------------------
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
(Bonn).
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.
-------------------------------------------------------------------------
King,R.Bruce
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-
fold
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.
-------------------------------------------------------------------------
Mezey,P.G.
University of Saskatchewan
Saskatchewan, Canada
"Topological Methods of Molecular Shape Analysis"
-------------------------------------------------------------------------
Ohlenbusch, Helgo M.,
Worcester Polytechnic Institute (MA)
USA
(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
simulations.
-------------------------------------------------------------------------
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
IMFM/TCS
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
Zerovnik.
-------------------------------------------------------------------------
Quinn, C.M.
National University of Ireland
Department of Chemistry
Ireland
"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
presented.
-------------------------------------------------------------------------
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
E.N.S.A.M.
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
arguments.
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
Trihealth
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.