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

摘要: The graph isomorphism problem belongs to the class of NP problems, and has been conjectured intractable, although probably not NP-complete. However, in context chemistry, because molecules are a restricted graphs, can be solved efficiently (i.e., polynomial-time). This paper presents theoretical results that for all molecules, problems isomorphism, automorphism partitioning, canonical labeling polynomial-time problems. Simple algorithms also given planar molecular graphs used partitioning paraffins, polycyclic aromatic hydrocarbons (PAHs), fullerenes, nanotubes.