Matrix-coded trees

Lukovits (2000, 2002, 2004) and Lukovits and Gutman (2002) offered an approach by which the vertex-adjacency matrix of an acyclic structure can be replaced by a single number, called the compressed (vertex-) adjacency matrix code, denoted by CAM. Here we present, besides the CAM code, the N-tuple code of trees that induces the unique labeling of trees (Aringhieri et al 1999). A graph is acyclic if it does not contain cycles. A tree is a connected acyclic graph. 

Challacombe, M., Schwegler, E., Almlof, J., 1996, Fast Assembly of the Coulomb Matrix A Quantum Chemical Tree Code , J. Chem. Phys., 104, 4685. 

Challacombe, M. E. Schwegler, and J. Almlof. 1996. Fast assembly of the Coulomb matrix A quantum chemical tree code. J. Chem. Phys. 104,4686. 

Figure 1 Physical tree depicting the carbon skeleton of 3-methyl-4-ethylhexane, the upper-half of the corresponding vertex-adjacency matrix and the CAM code...

The structure of the vertex-adjacency matrix is such that it contains only one nonzero element in each column of its upper (or in each row of its lower) triangle. This fact allows one to replace the vertex-adjacency matrix by the CAM code. Each digit in the CAM code denotes the row in the upper-half of the vertex-adjacency matrix in which the digit 1 is placed. Thus, the CAM code is a linear representation of the vertex-adjacency matrix composed of T - 1 entries. Different tree-labelings lead to a different CAM. The resulting CAM code of T, is 12342111. It should be also noted that the CAM code can be determined directly by inspecting the labeling of a tree. 

The vertex-adjacency matrix and the corresponding tree can be easily recovered from the CAM code. Let us consider the following CAM code 12335567. This code represents the compact form of the following matrix ... 

The quantum-chemical tree code (QCTC) [M. Challacombe and E. Schwegler, J. Chem. Phys., 106, 5526 (1997)] is a modification of the classical tree-code method. The QCTC method allows calculation of the matrix elements of the Coulomb matrix J for large molecules in a time that is proportional to the number of basis functions b this calculation is 0 b), and one says that the calculation exhibits linear scaling with size of the molecule. Challacombe and Schwegler used the QCTC method to do an ab initio SCE MO calculation on the 698-atom monomer of the P53 protein at a fixed geometry (obtained from a protein data bank) using the 3-21G basis set (3836 basis functions). They then calculated the molecular electrostatic potential (Section 15.7) of the P53 monomer. (The P53 protein is a tetramer and acts as a tumor suppressor. Mutations in the gene for this protein are found in half of human cancers.)... 

Assembly of the Coulomb Matrix A Quantum Chemical Tree Code. 

---