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.