G1 The aim of this book is to present a number of the graph-theoretical matrices that are frequently encountered in chemical graph theory. Matrices are convenient devices for the algebraic representation of graphs — they allow numerical handling of graphs [e.g., 31-36]. A graph is a mathematical object, usually denoted by G, which consists of two non-empty sets; one set, usually denoted by V, is a set of elements called vertices and the other, usually denoted by E, is a set of unordered pairs of distinct elements of V called edges [11]. Thus, G=(V,E). Note in the parlance of Harary [12] vertices are called points and edges lines.
We are here concerned with a special class of graphs called chemical graphs, that is, graphs representing chemical structures. If chemical structures under consideration are molecules, we call this type of chemical graphs molecular graphs. They are generated by replacing atoms and bonds with vertices and edges, respectively [2,26]. Hydrogen atoms are ordinarily neglected. A picture of a hydrogen-depleted simple molecular graph G1 representing 1-ethyl-2-methylcyclobutane is given in Figure 1.
A simple graph is defined as a graph that contains no multiple edges or loops. Two or more edges that join a pair of vertices are called multiple edges. A graph containing multiple edges is called the multiple graph or multigraph [12]. A loop is an edge joining a vertex to itself. Graphs containing multiple edges and loops are called general graphs [11].
Labeling vertices and edges of a graph is important, because the structure of any graph-theoretical matrix depends on the labeling [2]. In other words, two graphs may be identical, but because they are differently labeled, the corresponding matrices will appear to be different in their manifested arrangements.
Figure 1. 1-ethyl-2-methylcyclobutane and the corresponding hydrogen-depleted molecular graph G1.
The book is structured as follows: the second chapter exposes the adjacency matrix and related matrices, the third chapter the incidence matrices, the fourth chapter the distance matrix and related matrices, the fifth chapter a number of special matrices and the sixth chapter the graphical matrices. We end the book with concluding remarks and an extensive list of references.
