Chemical Graph Theory

Introduction and Fundamentals

D Bonchev

• Publisher: CRC Press
• Year: 2018
• Print ISBN: 9780856264542
• eBook ISBN: 9781351461597
• Edition: 1
• Topic: Physical Sciences
• Subtopic: Industrial & Technical Chemistry

This volume presents the fundamentals of graph theory and then goes on to discuss specific chemical applications. Chapter 1 provides a historical setting for the current upsurge of interest in chemical graph theory. Chapter 2 gives a full background of the basic ideas and mathematical formalism of graph theory and includes such chemically relevant notions as connectedness, graph matrix representations, metric properties, symmetry and operations on graphs. This is followed by a discussion on chemical nomenclature and the trends in its rationalization by using graph theory, which has important implications for the storage and retrieval of chemical information. This volume also contains a detailed discussion of the relevance of graph-theoretical polynomials; it describes methodologies for the enumeration of isomers, incorporating the classical Polya method, as well as more recent approaches.

Chapter 1

THE ORIGINS OF CHEMICAL GRAPH THEORY

Dennis H. Rouvray

Department of Chemistry, University of Georgia, Athens, GA 30602, USA

1. Introduction

2. The First Use of Chemical Graphs

3. The Emergence of Structure Theory

4. The Concept of Valence

5. The Growth of Chemical Graph Theory

6. Isomer Enumeration Techniques

7. Early Additivity Studies

8. The Introduction of Topological Indices

9. Elementary Bonding Theory

10. Conclusion

11. References

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. Pure 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 hypothetico-deductive constructs, are tied to concrete 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 Pregel 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 numerous practical problems, and today still retains an applied character. In the early days, very important strides were made in the development of graph theory by the investigation of some very concrete problems, e.g. Kirchhoff’s study of electrical circuits [8], and Cayley’s attempts to enumerate chemical isomers [9]. Further details on the history of graph theory may be obtained from the monograph by Biggs et al. [10]; two recent papers by Wilson [11,12] have also discussed the subject.

Before delving into those aspects of graph theory which relate specifically to chemistry, it is appropriate to make some comment on the term graph itself and its origins. We feel that it is not sufficiently widely known either by mathematicians or chemists that the term is of chemical origin. Although the word graph was first introduced into the literature by the mathematician Sylvester [13], it was derived by him from a contemporary chemical term. At the time, the chemical structure of a molecule was described as the “graphical notation” of a molecule. Sylvester felt that the word graph would be a convenient abbreviation for this chemical term. It was, of course, unfortunate that the word graph had already been applied in another context, namely, to describe cartesian data plots. However, the terminology has now become so well established that it is too late to consider making changes. It is therefore necessary to live with the fact that the word graph is used to describe two different concepts in mathematics, which are in no way related to one another.

1.2 The First Use of Chemical Graphs

Much of the current panorama of chemical theory has been erected on foundations that are essentially graph-theoretical in nature. Chemical graphs are now being used for many different purposes in all the major branches of chemistry. The present widespread usage of the chemical graph renders the origins of the earliest implicit application of graph theory of some considerable interest. Chemical graphs were first introduced in the latter half of the eighteenth century. To understand the need for them at that time and the circumstances of their introduction into the chemical literature, it will be necessary to say something about the prevailing attitudes in eighteenth century chemistry. Chemical thinking in the eighteenth century was steeped in Newtonian ideas, especially those pertaining to the internal structure of matter and the short-range forces existing between particles. In 1687 Newton himself had stated [14] that all natural phenomema depend “upon certain for...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• 1. THE ORIGINS OF CHEMICAL GRAPH THEORY
• 2. ELEMENTS OF GRAPH THEORY FOR CHEMISTS
• 3. NOMENCLATURE OF CHEMICAL COMPOUNDS
• 4. POLYNOMIALS IN GRAPH THEORY
• 5. ENUMERATION OF ISOMERS
• 6. GRAPH THEORY AND MOLECULAR ORBITALS
• INDEX