MATHEMATICAL CHEMISTRY SERIES Editors: D. Bonchev and D.H. Rouvray CHEMICAL GRAPH THEORY INTRODUCTION AND FUNDAMENTALS D. BONCHEV and D.H. ROUVRAY Z [ ABACUS PRESS/GORDON & BREACH SCIENCE PUBLISHERS CONTENTS 1. THE ORIGINS OF CHEMICAL GRAPH THEORY Dennis H> Rouvray 1 1. Introduction 1 2. The First Use of Chemical Graphs 3 3. The Emergence of Structure Theory 5 4. The Concept of Valence 10 5. The Growth of Chemical Graph Theory 16 Ó. Isomer Enumeration Techniques 18 7. Early Additivity Studies 22 8. The Introduction of Topological Indices 26 9. Elementary Bonding Theory 30 10. Conclusion 33 It References 34 2. ELEMENTS OF GRAPH THEORY FOR CHEMISTS Oskar E Poiansky 42 1, What is a Graph and What Kinds of Graph Exist? 42 2. Some Graph-theoretical Terms 45 3. Connectedness of Graphs 47 4. Partitioning of a Graph 54 5. Planarity of Graphs 57 6. Line Graphs 62 7. Operations on Graphs 63 8. The Automorphism Group of a Graph 67 9. Matrix Representation and Eigenvalue Problems of Undirected Graphs 78 10* The Matrix Représentation of Digraphs 83 II. Distances in Graphs and Digraphs 85 12. Metric and Topological Spaces for Simple Graphs 89 13. Graphs in Quantum Chemistry 93 14. Weighted Graphs 93 15. Bibliography 94 Acknowledgment 96 3. NOMENCLATURE OF CHEMICAL COMPOUNDS Alan L Goodson 97 1. Introduction 97 2. Development of Chemical Nomenclature 101 3. Development of Chemical Line Notations 105 4. Development of Graph Theory 107 V Material chroniony prawem autori Ы Canients 5. Application of Graph Theory to Chemical Nomenclature 108 6. Summary 124 L￿ References and Notes 125 4. POLYNOMIALS IN GRAPH THEORY Ivan Gutman 133 1. Why Polynomials in Graph Theory? 133 г On Chemical Applications of Graphic Polynomials 135 3. Polynomials 136 4. The Characteristic Polynomial 137 5. The Matching Polynomial 150 6. More Graphic Polynomials 164 7. References 169 5. ENUMERATION OF ISOMERS Alexandria T. Balaban 177 1 Introduction 178 2. Definitions and Mathematical Background 179 3, Historical 184 4. Pól ya' s Theorem 187 5. Generalized Pól ya Theorem 197 1 6. Ruch s Double Cosct Formalism 200 7. De Bruijn-Harary-Palmer Power Group Theory 202 8. Valence Isomers 203 9. Polyhexes 210 10. Diamond Hydrocarbons and Staggered Alkane Rotamers 215 11. Diasiereomeric Annulcnes 216 12. Isomers and Computer Programs for Their Generation 219 13. Isomerism and Reaction Graphs 222 14. Conclusion 224 References 226 6 GRAPH THEORY AND MOLECULAR ORBITALS Ne nad Trìnajstié 235 1 Introduction 236 2. Elements of Graph Spectral Theory 237 3. The Essence of Hückel Theory 244 4. Isomorphism of Hückel Theory and Graph Spectral Theory 248 5. The Spectrum of a Hückel Graph 249 6. The Number Non-bonding Molecular Orbitais 251 7. Total rc-Electron Energy 255 8. Topological Resonance Energy 262 9. Concluding Remarks 272 10. References 273 281 INDEX Materiał chroniony prawem au: • INTRODUCTION TO THE SERIES The mathematization of chemistry has a long and colorful history extending back well over two centuries. At any period in the development of chemistry the extent of the mathematization process roughly parallels the progress of chemistry as a whole. Thus, in 1786 the German philosopher Immanuel Kant observed that the chemistry of his day could not qualify as one of the natural sciences because of its insufficient degree of mathematization. It was not until almost a century later that the process really began to take hold. In 1874 one of the great pioneers of chemical structure theory, Alexander Crum Brown (1838-1922) prophesied that "...chemistry will become a branch of applied mathematics; but it will not cease to be an experimental science. Mathematics may enable us retrospectively to justify results obtained by experiment, may point out useful lines of research and even sometimes predict entirely novel discoveries. We do not know when the change will take place, or whether it will be gradual or sudden...." This prophecy was soon to be fulfilled. Indeed, even before these words were uttered, combinatorial methods were being employed for the enumeration of isomeric species. During Crum Brown's lifetime algebraic equations were used to predict the properties of substances, calculus was employed in the description of thermodynamic and kinetic behavior of chemical systems, and graph theory was adapted for the structural characterization of molecular species. In the present century the applications of mathematics have come thick and fast. The advent of quantum chemistry in the 1920s brought in its wake a host of mathematical disciplines that chemists felt obliged to master. These included several areas of linear algebra, such as matrix theory and group theory, as well as calculus. Group theory has now become so widely accepted by chemists that it is now used routinely in areas such as crystallography and molecular structure analysis. Graph theory seems to be following in the footsteps of group theory and is currently being exploited in a wide range of applications involving the classification, system atiza tion, enumeration and design of systems of chemical interest. Topology has found important applications in areas as diverse as the characterization of potential energy surfaces, the discussion of chira lity, and the description of catenated and knotted molecular species. Information theory has yielded valuable insights into the nature of thermodynamic processes and the origin of life. The contemporary vu Material chroniony prawem autorskim vai Introduction to thè Series fascination with dissi pa ti ve systems, fractal phenomena and chaotic behavior has again introduced new mathematics, such as catastrophe theory and fractal geometry, to the chemist All of these and numerous other applications of mathematics that have been made in the chemical domain have brought us to a point where we consider it may now be fairly said that mathematics plays an indispensible role in modern chemistry. Because of the burgeoning use of mathematics by chemists and the current feeling that mathematics is opening up some very exciting new directions to explore, we believe that the 1990s represent a particularly auspicious time to present a comprehensive treatment of the manifold applications of mathematics to chemistry. We were persuaded to undertake this somewhat awesome task after much reflection and eventually decided to publish our material in a series of volumes, each of which is to be devoted to a discussion of the applications of a specific branch of mathematics. The title of our series, Mathematical Chemistry, was chosen to reflect as accurately as possible the proposed contents. The term "mathematical chemistry" was coined in the early 1980s to designate the field that concerns itself with the novel and nontrivial application of mathematics to chemistry. Following the usual practice in this area, we shall interpret chemistry very broadly to include not only the traditional disciplines of inorganic, organic and physical chemistry but also ite hybrid offspring such as chemical physics and biochemistry. It is anticipated that each of the volumes in our series will contain five to six separate chapters, each of which will be authored by a leading expert in the respective field. Whenever it is evident that one such volume is insufficient to do justice to a wealth of subject matter, additional volumes devoted to applications of the same branch of mathematics will be published. In this way it is hoped that our coverage will indeed be comprehensive and reflect significant developments made up to the end of the twentieth century. Our aim will be not only to provide a background survey of the various areas we cover but also to discuss important current issues and problems, and perhaps point to some of the major trends that might be reasonably expected in mathematical chemistry in the early part of the new millennium. In the first few volumes of our series we propose to examine the applications to chemistry of graph theory, group theory, topology, combinatorics, information theory and artificial intelligence. It may be of interest to observe here that mathematical chemists have often applied and even sought after branches of mathematics that have tended to be overlooked by the chemical community at large. This is not to imply that the mathematics itself is necessarily new — in fact, it may be quite old. What is new is the application to chemistry; this is why the word novel was employed in our earlier definition of mathematical chemistry. The thrill of discovering and developing some novel application in this sense has been an important source of motivation for many mathematical chemists. The other adjective used in our definition of mathematical Material chroniony prawem autorskim lnlroductton to lhe Series LX chemistry, i.e. nontrivial, is also worthy of brief comment To yield profitable new insights, the mathematics exploited in a chemical context usually needs to be of at least a reasonably high level. In an endeavor to maintain a uniformly high level, we shall seek to ensure that all of the contributions to our volumes are written by researchers at the forefront of their respective disciplines. As a consequence, the contents of our various volumes are likely to appeal to a fairly sophisticated audience: bright undergraduate and postgraduate students, researchers operating at the tertiary level in academia, industry or government service, and perhaps even to newcomers to the area desirous of experiencing an invigorating excursion through the realms of mathematical chemistry. Overall, we hope that our series will provide a valuable resource for scientists and mathematicians seeking an authoritative and detailed account of mathematical techniques to chemistry. In conclusion, we would like to take this opportunity of thanking all our authors, both those who have contributed chapters so far and those who have agreed to submit contributions for forthcoming volumes. We should also like to thank our publisher, Gordon and Breach, for supporting us in this project and bringing out what we feel is a timely and worthwhile addition to the literature on mathematical chemistry. Finally, it is our sincere hope that the material to be presented in our series will find resonance with our readership and afford many hours of enjoyable and stimulating reading. Danai I Bonchev and Dennis //. Rouvray 1. 1. Kant, Metaphysiche Anfangsgründe der Naturwissenschaft, Hartknoch Verlag, Riga, 1786. 2. A. Crum Brown, Rept BriL Assoc. Sci., 45-50,1874. 3. F.M Flavitsky, У. Russ, Chenu Soc 3,160.1871. Materiał chroniony prawem aur PREFACE The present work is the first of the volumes to appear in our new series entitled Mathematical Chemistry. As such, it represents the initial opus in what we anticipate will become an ongoing series of works devoted to discussion of the major applications of mathematics to chemistry. In our opening foray into the domain of mathematical chemistry we have elected to focus on the chemical applications to graph theory. This volume is intended to provide a useful introduction to the area by treating the fundamentals of the subject and some of its more important applications. Graph theory was chosen as our theme because its story typifies what is happening with many of the newer applications of mathematics in the chemical context The applications and the number of publications deriving from chemical graph theory have grown enormously, starting from a mere trickle two decades ago and developing into the torrent that confronts us today. Graph theory has been employed in the classification, enumeration, system a tization and design of many different kinds of system of chemical interest, ranging from individual molecules to complex reaction networks. Its potential for generating new concepts based on the structure of chemical systems and its capacity to reveal regularities in chemical data sets have rendered it a very valuable tool in the chemist's current arsenal. Moreover, because of the great generality of graph-theoretical methods, analogies between seemingly unrelated chemical systems and problems can often be discerned. It is our aim here to introduce the reader to some of the exciting possibilities that graph theory has to offer the chemist In Chapter 1 Rouvray surveys the development of chemical graph theory from a historical perspective, tracing the subject from its origins over 200 years ago down to the present day. Chapter 2 by Polansky provides an outline of the basic ideas and mathematical formalism of graph theory. Starting from the concept of the graph, Polansky proceeds to discuss such chemically relevant notations such as connectedness, graph matrix representations, metric properties, symmetry and operations on graphs. Having been thus primed, the reader is then led in Chapter 3 by Goodson into a discussion on the role of graphs in chemical nomenclature. This topic, which is all too often neglected by the chemist, is worthy of serious treatment because it has important implications for the storage and retrieval of chemical information. An intriguing discussion then follows on the relevance of graph-theoretical polynomials in Chapter 4 by Gutman. m xt l Material chroniony prawem autorskim xii Preface Many specific types of polynomial, such as the characteristic and matching polynomials, are introduced and their uses described. Chapter 5 by Balaban deals with the methodology of isomer enumeration, a field that continues to challenge us with many fascinating problems. Balaban's discussion embraces not only the traditional techniques adopted for enumeration of chemical species, such as the now classic Pólya method, but also delves into more recent approaches developed by workers such as Ruch and De Bruijn, Harary and Palmer. Our final Chapter by Trinajstic elucidates the interplay between graph theory and molecular orbital theory from the standpoint of spectral graph theory, and highlights in particular the concept of topological resonance in molecular species. To conclude we should like to acknowledge a profound debt of gratitude to our many colleagues—too numerous to mention here by name—currently working in the field of chemical graph theory. Without their continual encouragement and support our own involvement in this field over the past two decades would not have been nearly as enjoyable and fulfilling. We can only hope that some of the stimulation and excitement that we have experienced will be shared by our readers. If this proves to be the case and eventually leads to their own contribution to the field we shall be well pleased Danail Bonchev and Dennis //. Rouvray Material chroniony prawem autorskim Chapter 1 THE ORIGINS OF CHEMICAL GRAPH THEORY Dennis H. Rouvray Department of Chemistry, University of Georgia, Athens, GA 30602, USA 1, Introduction 1 2, The First Use of Chemical Graphs 3 3, The Emergence of Structure Theory 5 4» The Concept of Valence 10 5. The Growth of Chemical Graph Theory 16 6. Isomer Enumeration Techniques 18 7. Early Additivity Studies 22 8. The Introduction of Topological Indices 26 9. Elementary Bonding Theory 30 10. Conclusion 33 11. References • • •. 34 1.1 Introduction It has frequently been remarked that mathematics is a more effective tool in the natural sciences than might be reasonably expected [1]. At first sight, the evident power of mathematics may indeed seem surprising, though more mature reflection on this theme leads us to anticipate the validity of mathematics in the description of the real world. Pore mathematics is founded on sets of axiomatic systems that form the basis for hypothetico-deductive theories of relations. Although in general not derived from observation of the real world, mathematical axioms do not normally violate observable phenomena. The natural sciences, however, which also employ hy pot heti co-deductive constructs, are tied to concrete 1 Material chroniony prawem autori t Chemical Graph Theory interpretation. The axioms upon which the sciences are built (the so￿ called laws of nature) must accord with observations of the real world. Since reality is constituted in the interaction of consciousness with an environment, any conceptual scheme of reality automatically reflects the processes occurring in the consciousness and the environment [2]. As products of the mind, both mathematical and scientific axioms will have a structure imposed on them [3] that is determined by the neural networks constituting the human brain [4]. The situation has been summed up by Weyl [5], who stated that "It would be folly to expect cognition to reveal to intuition some secret essence of things hidden behind what is manifestly given by intuition." Viewed in this light, the various kinds of mathematics that have flourished in the past, and that might conceivably be developed in the future, can be regarded as potential starting points for construction of all the different possible sciences. The scientist thus plays the key role of establishing isomorphic relations between areas of mathematics and branches of science. This is usually accomplished by selecting appropriate structures from the mathematical storehouse and identifying them with scientific concepts. Relationships which are verified in the one domain then become of immediate applicability in the other domain. Results obtained or insights gained in the one system can thus be assumed to be directly transferable to the other. A classic example of this concordance of mathematics and science forms the subject matter of this chapter. We shall examine here the manifold interactions of the mathematical discipline of graph theory with the science of chemistry. In particular, we shall be tracing the origins of the interaction and focus on the early historical development of the field which has become widely known today as chemical graph theory. Graph theory itself has a long and colorful history; the few words we now devote to this topic form a convenient departure point for the rest of our narrative. Graph theory is one of the few branches of mathematics that may be said to have a precise starting date [6]. In 1736, Euler [7] solved a celebrated problem, known as the Königsberg bridges problem. The question had been posed whether it was possible to walk over all the seven bridges spanning the river Prege￿ in Königsberg just once without retracing one's footsteps. Euler reduced the question to a graph￿ theoretical problem, and found an ingenious solution [7]. Euler's solution marked not only the introduction of the discipline of graph theory per se, but also the first application of the discipline to a specific problem. Since its inception, graph theory has been exploited for the solution of Materiał chroniony prawem autorski