Canonical labeling

WC. Herndon, Canonical labelling and linear notation for chemical graphs, in Chemical AppUcations of Topology and Graph Theory, R.B. King (Ed.), Elsevier, Amsterdam, 1983, pp. 231-242. 

Balaban S, Filip PA, Ivanciuc O, Computer generation of acyclic graphs based on local vertex invariants and topological indices derived canonical labelling and coding of trees and alkanes, J. Math. Chem., 11 79-105, 1992. 

Balaban, T.-S., Filip, P. and Ivanciuc, O. (1992). Computer Generation of Acyclic Graphs Based on Local Vertex Invariants and Topological Indices. Derived Canonical Labelling and Coding of Trees and Alkanes. J.Math.Chem., 11,79-105. 

Faulon, J.-L. (1998). Isomorphism, Automorphism Partitioning, and Canonical Labeling Can Be Solved in Polynomial-Time for Molecular Graphs. J.Chem.lnf.Comput.Scl, 38,432-444. 

Derived canonical labelling and coding of trees and alkanes./. Math. Chem., 11, 79—105. 

Faulon, J.-L. (1998) Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs. J. Chem. Inf. Comput. Sci., 38, 432-444. 

M. RandiC, Distance-based canonical labels, Croat. Chem. Acta (submitted). 

Partitioning, and Canonical Labeling Can Be Solved in Polynomial-Time for Molecular Graphs. 

In row (1) the reactants are brought into a canonical form, duplicates are eliminated and the canonically labeled structures are assigned to q. Row (4) is central to Algorithm 5.15. It yields the new structures j. from the partial libraries generated earlier, j and i e k. The process of generation is hnished as soon as no further structures are generated. This is checked by row (2). 

B. McKay. Computing automorphisms and canonical labelling of graphs. In Proc. Intern. Conf. on Combinatorial Theory, Lecture Notes in Mathematics No. 686, pages 223-232. Springer, Berlin, 1977. 

FIGURE 2.19 3-D carbon skeleton of the diamantane C14H20 molecule, which consists of two fused adamantane units with canonical labels. 

In continuation, as outlined in Appendix 8, label 14 has only one site where it must go, which is also the case with label 13. The next smallest labels have two possibilities, but all the remaining labels have unique locations and could not be assigned to alternative neighboring locations. Thus, one finds that the total number of symmetry operations for diamantane, which is equal to the number of alternative labeling of vertices that will produce the same adjacency matrix, is 6 x 2 = 12. In Appendix 9, we show the 12 possible canonical labels for diamantane, and in Table 2.3, we have listed all 12 permutations of labels that leave the adjacency matrix invariant. As one... 

For a graph G considered one has to select canonical labels for vertices. Recall that there are several alternative canonical labelings. 

We have selected canonical labels that will produce, for the adjacency matrix, the smallest binary number when its rows are read from left to right and from top to bottom. 

FIGURE 8.3 (a) Azulene and its canonical labels, (b) The canonical spanning tree of azulene. 

FIGURE 8.4 Construction of the canonical labels for carbon skeleton of adamantane. 

We will consider now adamantane, for which we have already described the assignment of the canonical labels. We have selected adamantane for the following reasons (i) It requires about half a dozen trials to find canonical labels one labeling among 10 = 3,628,800 (ii) it is a beautiful molecule, and (iii) it was, for the first time, synthesized by Prelog and Seiwerth [63] in our neighborhood, Zagreb, Croatia, about 80 years ago. Admittedly, at the time, some of us were not yet around. 

Having canonical labels for vertices of adamantane, we can initiate construction of the Walk Above code. To obtain the Walk Above code, one starts with vertex label 1, and following the rules listed before, arrive at the walk ... 

The canonical labeling of fibonacenes appears chaotic, but in fact, there is a hidden regularity, which can be seen in the second row of Figure 8.8, which illustrates the canonical spanning trees for the four fibonacenes, which have simple appearance. They... 

FIGURE 8.8 In the first row for the leading members of fibonacenes phenanthrene, chrysene, picene, and fulminene (first row) we show their canonical labels. In the second row we show their canonical spanning trees. In third row we show canonical labels of the spanning trees, which belong to the ring closure bonds. 

---