Graphical Modeling of Combinatorial Chemistry

Shinsaku FUJITA and Sherif EL-BASIL


1 Introduction

Traditional textbooks [1 - 3] on chemical group theory deal with linear representations and character tables of groups, which are usually directed to modeling molecular vibrations, infrared spectroscopy, and symmetry-simplification of secular-determinants in molecular orbital calculations. On the other hand, Fujita [4] adopted an alternative approach which is based on permutation representations (coset representations) and mark tables}, where he developed the USCI (unit-subduced-cycle-index) method [4, 5], aiming at studying combinatorial enumeration in chemistry.
The two approaches of chemical group theory have been compared [6] after the development of the characteristic-monomial method for combinatorial enumeration on the basis of the former approach [7, 8]. While the former approach requires conjugacy relations between elements of a group only, the latter approach requires a knowledge of all group/subgroup relations which may not be trivial to find out.
Usually a group G is expressed as the set of elements of symmetry g's which it contains:

where |G| is the order of G and g1 = I (the identity element). The set of elements of symmetry generates a sequence of subgroups (SSG), which are usually ordered in a nondescending way of their orders:

in which G1 = C1 = {I} and Gs = G. Each subgroup Gi (1 <= i <= s) is selected as a representative of conjugate subgroups and may be used to express G as a (right) coset. Thus, a set of cosets may be defined by:

where r represents the number of cosets in the coset decomposition expressed by:

Equation 3 allows one to generate a set of permutations G(/Gi) given by:

where each permutation pg is expressed by:

The set of permutations (eq. 5) is called coset representation, the symbol of which has been coined as G(/Gi) in order to emphasize the distinction between the global (G) and the local symmetry (Gi) [9]. Equations 5 and 6 allow the computation of marks of G as the numbers of cosets which are stabilized by Gj's (1 <= j <= s). When the above types of computation is repeated for all values of i = [1, s] and j = [1, s], the table of marks of G results.
Fujita showed how to use such a table of marks to specify the type of orbit which controls substitution pattern in a given graph [4, 5]. Thus, when this orbit of substitution is specified, it is subdued by all subgroups of G, as expressed by

where Gi, Gj, Gk, and Gl are all subgroups of G, while Gk Gl, ... are subgroups of the (subducing) subgroup Gj. Thereby, monomial expressions called unit subduced cycle indices (USCI's) are obtained as general formulas [4, 5]:

where one places djk = |Gj|/|Gk|, djl = |Gj|/|Gl}|, and so on and selects the superscripts from the multiplicity factors bjk, bjk, etc. in eq. 7. Naturally, when Gi is equal to C1= {I} in eq. 5, the regular representation G(/C1) results.
In general, coset representations (CR's) and their subductions control orbits (equivalence classes) of ligands or vertices in a molecule or graph [10 - 12] as well as orbits (equivalence classes) of isomeric molecules or graphs (configurations) [4, 5]. The latter point is an essence of combinatorial enumeration (cf. Chapter 15 of Ref. [4]); however, it has been discussed rather mathematically and abstractly in the formulation of theorems for combinatorial enumeration, as pointed out in a recent review [13]. Although a few exceptional efforts have recently appeared [14 - 16], further studies would be desirable so as to make up for such situations, especially, when the education or popularization of these concepts is taken into consideration.
It is the main objective of this work to model the above abstract concepts such as CR's, marks, subductions, and USCI's by using (colored) graphs which can easily be generated by experimental chemists by analogy with "derivatives by substitution".

2 Modeling Coset Representations and Marks

As an illustration, one considers the D4h-group given by:

These symmetry elements are designated in a graph model of D4h depicted in Figure 1.

Figure 1. A moldel of the D4h-group. The vertical mirror planes sv and sv respectively contain two-fold rotation axes C2(v) and C2(v), while the diagonal mirror planes sd and sd respectively contain two-fold axes C2(d) and C2(d), which are perpendicular to each other and in paper-plane. The inversion i and the horizontal mirror plane sh are not depicted.

Let us consider Gi = C2h = {I, C2, sh, i}, which is one of the twenty-seven subgroups of D4h (up to conjugacy). Then, the cosets of this case are obtained as follows according to eq. 3:

After numbering the cosets sequentially as above, eqs. 5 and 6 are applied to give the permutations shown in Table 1.

Table 1. Coset Representation of D4h(/C2h)

By starting from the permutation representation (Table 1), one obtains a fixed-point vector (FPV) as a row vector:

For example, the checked elements in the Cs-column of Table 1 indicate that the number of fixed cosets is equal to 4 so that the value for Cs in the FPV (eq. 11) is placed to be 4. The FPV constructs the row of D4h(/C2h) in the mark table of D4h, the full list of which has been reported elsewhere [17].
Permutations of a coset representation such as listed in Table 1 are modeled by a set of colored graphs called homomers which is given by

so that a one-to-one function exists, i.e.,

This has been generally proved previously (Theorem 15.2 of [4]). It should be noted that the present term "homomer" designates both homomers and enantiomers from the stereochemical point of view.
To obtain such homomers (colored graphs), one proceeds as follows:

  1. Finding a parent graph: Find a graph which models the identity representation G(/G). This graph has once been discussed in terms of regular bodies [10]. This graph has two properties.
    1. It has |G| number of vertices, which are governed by the regular representation G(/C1).
    2. It stays fixed under the action of all of the elements of G.
    Thus, this graph is a single uncolored graph, i.e., H[G(/G)] = {h}, which may be here called the parent graph of the group G.
  2. Partition of vertices: Graphs which model other coset representations are colored graphs because they represent reduction of the symmetry of the parent graph h. The term "coloring" is the mathematical synonym of "substitution" in chemistry, which has been once discussed in terms of subductive and inductive derivation [11, 12]. Thus, to find H[G(/Gi)] = {h1, h2,..., hr}, one applies all of the elements of Gi on an appropriate vertex (va) of the parent graph h, where one can obtain a set of equivalent vertices, e.g., (va vb vc vd). Among the remaining vertices of h, one next selects a vertex ve and the same operation is conducted to give another set of equivalent vertices, e.g., (ve vf vg vh). Such an operation is repeated to cover all of the vertices of h to obtain a product of "color identities" (va vb vc vd)(ve vf vg vh)... as a vertex partition, where the number of vertices in every set has been previously proved to be equal to |Gi| in general (Lemma 2 of [10]).
  3. Selecting a starting homomer: The vertices of an arbitrary set are colored in black, where one selects the number of black (colored) vertices to be smaller than (or equal to) the number of white (uncolored) vertices. It should be noted that, generally speaking, the coloring of the first set (va vb vc vd), the second set (ve vf vg vh), etc. produces isomers of the Gi-symmetry but not always homomers (cf. Lemma 2 and Theorem 1 of [10]). Among such isomers, one selects an arbitrary one as h1.
  4. Generating a homomer set: The resulting colored homomer, h1, is operated upon by the elements of G to generate the full set of (symmetry equivalent) graphs H[|G(/|Gi)] = {h1,h2,...,hr}.
For example, let us consider D4h(/C2h), the parent graph h of which is depicted in Figure 1. The numbering of vertices can be selected arbitrarily, as found in Figure 1. Then, one selects vertex 1, which is moved by the elements of C2h ={I, C2, sh, i}. Thereby, one obtains a set of equivalent vertices (1 5 9 13), which are colored in black so as to give a homomer h1 shown in Figure 2. By applying the representative C4 of the coset C2hC4 (eq. 10) to the first homomer h1, its numbering is changed to the second homomer h2, in which vertices 1, 5, 9, 13 are colored in black. Note that each element of the coset C2hC4 produces the identical homomer h2, although the numbering may alter according to the element. On the same line, the applications of C2(d) (ÎC2hC2(d)) and C2(v) (ÎC2hC2(v)) yield homomers h3 and h4, respectively. As a result, it can be shown that the set H[D4h(/C2h)] experiences the bijection, h1® 1, h2® 2, h3® 3, and h4® 4, where the cosets at issue are numbered as shown in eq. 10.

Figure 2. H[D4(/C2h)] = {h1,h2,h3,h4}. The four homomers which model D4h(/C2h) and generate the permutations in Table 1 when hi's are moved over i = [1,4]. All of the four homomers are stabilized (fixed) under the action of C1, C2, Cs, Ci, and C2h, leading to the mark row (the FPV) given by eq. 11.

As found easily by the procedure described in the preceding paragraph, each element of the coset C2hI fixes all of the homomers (h1, h2, h3, and h4), where this corresponds to the permutation (1)(2)(3)(4); each element of the coset C2hC4 exchanges the pair of h1 and h2 as well as the pair of h3 and h4, where this corresponds to the permutation (1 2)(3 4); each element of the coset C2hC2(d) exchanges the pair of h1 and h3 as well as the pair of h2 and h4, where this corresponds to the permutation (1 3)(2 4); and finally each element of the coset C2hC2(v) exchanges the pair of h1 and h4 as well as the pair of h2 and h3, where this corresponds to the permutation (1 4)(2 3). Thereby, one can obtain the permutations of D4h(/C2h) collected in Table 1. Moreover, all of the four homomers (Figure 2) are stabilized (fixed) under the action of C1, C2, Cs, Ci, and C2h so that their marks (the numbers of fixed homomers) are equal to 4, leading graphically tothe mark row (the FPV) given by eq. 11.
Let us next consider C4v(/Cs). The parent graph h which produces the colored graphs depicted in Figure 3 is selected by referring to the parent graph of D4h (Figure 1) so that the elements of C4v = {I, C4, C43, C2, sv, sv, sd, sd} are related to those illustrated in Figure 1. The numbering of vertices can be selected arbitrarily, as found in h1 of Figure 3. By considering a subgroup Cs = {I, sv}, one can obtain the corresponding cosets: CsI = {I, sv}, CsC4 = {C4, sd}, CsC2 = {C2, sv}, and CsC43 = {C43, sd}.

Figure 3. H[C4h(/Cs)] = {h1,h2,h3,hv4}. Subgroups which fix each homomer are indicated to generate the mark row (FPV) given by eq. 14.

The partition step described above is applied to this case so as to produce the vertex partition: (1 2)(3 8)(4 7)(5 6). When one selects the first set (1 2) of the vertex partition and colors the two vertices, one can produce the first colored graph h1 shown in Figure 3. The coloring of the second set (3 8) or (4 7) produces another graph h1, which is an isomer of h1.
By applying the representative C4 of the coset CsC4 to the first homomer h1, its numbering is changed to the second homomer h2, in which vertices 1 and 2 are colored in black, as shown in Figure 3. On the same line, the applications of C2 (ÎCsC2) and C43 (ÎCsC43) yield homomers h3 and h4, respectively (Figure 3). It follows that the four homomers of the homomer set H[C4v(/Cs)] exhibit one-to-one correspondence to the sets of cosets through their representatives.
By the inspection of Figure 3, one can immediately write the following mark row:

3 Modeling One-Dimensional Irreducible Representations

Fujita demonstrated that rows of marks may be resolved into sums of irreducible representations [10]. When a given row of marks contains only 2's and 0's, then it is the sum of totally symmetric representation (all characters are ones) and a one-dimensional irreducible representation [15]. Figure 4 portrays several colored graphs which model coset representations, marks, and one-dimensional representations for the group D4h.

Figure 4. Modeling coset representations, stabilizer subgroups, and one-dimensional irreducible representations. In all these cases, one has H = {h1,h2}, among which h1 is shown and h2 is the complement graph.

4 Modeling Group Subductions

To find G(/Gi)¯Gj, where Gi and Gj are both subgroups of G, one considers the set of permutations of G(/Gi), which remains after eliminating all permutations except those which correspond to Gj. Then the corresponding row of marks is expressed as the sum shown in eq. 7. Graphically, one might write the corresponding equations:

Figure 5 illustrates an example of eq. 15. The homomer set H[C3v(/Cs)] = {h1,h2,h3} shown in the top row of Figure 5 is divided into two sets, i.e., = {h1,h2} and {h3}, under the subduction into Cs. These subduced sets correspond to a homomer set H[Cs(/C1)] = {h1,h2} and a homomer set H[Cs(/Cs)] = {h}, respectively, as shown in the bottom row of Figure 5. To test such subductions, a systematic method based on Cayley graphs has been reported [14].

Figure 5. Modeling a group subduction represented by C3v(/Cs)¯Cs = Cs}(/C1) + Cs(/Cs).

A more direct model of G(/Gi)¯Gj would be helpful to understand the process of subduction. Thus, one first considers the case of G(/G)¯Gj. The corresponding homomer set H[G(/G)] contains only one (uncolored) graph (the parent graph). Obviously, one can find G(/G)¯Gj = Gj(/Gj), which corresponds to a homomer set H[Gj(/Gj)] containing one (uncolored) graph. This step corresponds to a kind of coloring other than the vertex coloring described in the preceding paragraphs. For example, Figure 6 illustrates a direct model for the subduction C3v(/C3v)¯Cs = Cs(/Cs), where the coloring ("substitution") of two bridgehead positions by nitrogens restricts the symmetry of the parent graph.

Figure 6. Direct modeling of a group subduction represented by C3v(/C3v)¯Cs = Cs(/Cs).

It should be noted that the left diagram for H[C3v(/C3v)] in Figure 6 contains a set of six equivalent vertices, while the right diagram for H[Cs(/Cs)] contains three pairs of equivalent vertices. Each of the three pairs indicates a parent graph representing H[Cs(/Cs)].
Keeping Figure 6 in mind, one considers a direct model for the subduction C3v(/Cs)¯Cs, as shown in Figure 7. The homomer set H[C3v(/Cs)] = {h1,h2,h3} shown in the top row of Figure 7 (the same as those in Figure 5) is divided into two sets, i.e., = {h1,h2} and = {h} by the symmetry restriction (into Cs) due to the bridgehead coloring by nitrogens, as shown in the bottom row of Figure 7. These subduced sets correspond to H[Cs(/C1)] and H[Cs(/Cs)], respectively. The comparison of Figure 7 with Figure 5 indicates that the two kinds of modeling for group subductions are closely related to each other.

Figure 7. Direct modeling of a group subduction represented by C3v(/Cs)¯Cs = Cs(/C1) + Cs(/Cs).

5 Conclusion

Four abstract concepts, i.e., coset representations, marks, characters, and group subductions, are modeled by using colored graphs and a set of symmetry operations. Thereby, their fruitful contents are so much visualized that one would get an intimate knowledge on these concepts.


[ 1] H. H. Jaffe and M. Orchin, Symmetry in Chemistry, Wiley, Chichester (1965).
[ 2] F. A. Cotton, Chemical Applications of Group Theory, Wiley-International, New York (1971).
[ 3] D. M. Bishop, Group Theory and Chemistry, Clarendon, Oxford (1973).
[ 4] S. Fujita, Symmetry and Combinatorial Enumeration in Chemistry, Springer-Verlag, Berlin-Heidelberg (1991).
[ 5] S. Fujita, Theor. Chim. Acta, 76, 247–268 (1989).
[ 6] S. Fujita, J. Math. Chem., 30, 249–270 (2001).
[ 7] S. Fujita, Theor. Chem. Acc., 99, 224–230 (1998).
[ 8] S. Fujita, Theor. Chem. Acc., 101, 409–420 (1999).
[ 9] S. Fujita, J. Am. Chem. Soc., 112, 3390–3397 (1990).
[10] S. Fujita, Theor. Chim. Acta, 78, 45–63 (1990).
[11] S. Fujita, Bull. Chem. Soc. Jpn, 64, 3313–3323 (1991).
[12] S. Fujita, J. Chem. Inf. Comput. Sci., 31, 540–546 (1991).
[13] S. El-Basil, MATCH, 46, 7–23 (2002).
[14] S. El-Basil, Combinatorial Organic Chemistry, An Educational Approach, Nova Scientific, New York (1999).
[15] S. Fujita and S. El-Basil, MATCH, 46, 121–135 (2002).
[16] S. Fujita and S. El-Basil, J. Math. Chem., 33, 255–277 (2003).
[17] S. Fujita, Helv. Chim. Acta, 85, 2440–2457 (2002).