A representation of chemical transformations by labeled graphs

A transitional labeling of a graphG is an assignment of one of the elements of the set (1, -1, 0) to each vertex and edge ofG so that each edge labeled 0 is incident only with vertices labeled 0, and no edge labeled 1 (respectively, -1) is incident with a vertex labeled -1 (respectively, 1). Chemical transformations can be represented by graphs possessing a transitional labeling. The positive (negative) graph of a transitional labelingt of a graphG is the subgraph ofG consisting of the nonnegative (nonpositive) elements ofG. The linking graph oft is the subgraph consisting of the zero elements ofG. A maximum common subgraph of two given graphsG1 andG2 is a graphF isomorphic to a common subgraph ofG1 andG2 such that the sum of the number of vertices and number of edges ofF is maximum. A transitional labelingt of a graphG is a transform if there exists an extensiont′ oft to a supergraphG′ of G such that the linking graph oft′ is a maximum common subgraph of the positive and negative graphs oft′. Transforms are used to model chemical reaction pathways. Transforms and related concepts are studied in this paper. A characterization of transforms is also given.