zbMATH — the first resource for mathematics

Optimized algorithm to find all symmetry-distinct maps of a graph: Application to topology-driven molecular design. (English) Zbl 1187.92085
Summary: We describe an optimized algorithm for finding all symmetry-distinct maps of a given graph. It contains significant improvements on the computing time by representing the maps as linear codes. In this way, the time consuming step of removing equivalent maps can be solved more efficiently by searching for a “minimal code”. As an example we apply the algorithm to the 32-vertex Dyck-graph for which more than 4 billion cases should be investigated. One of its most symmetrical maps forms an interesting blueprint for a hypothetical negatively curved carbon allotrope of genus 3.

92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
05C90 Applications of graph theory
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: DOI
[1] Balaban A.T.: Chemical Applications of Graph Theory. Academic Press, London (1976)
[2] Mohar B., Thomassen C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001) · Zbl 0979.05002
[3] Gross J.L., Tucker T.W.: Topological Graph Theory. Dover Publications, New York (2001) · Zbl 0991.05001
[4] Ceulemans A., Lijnen E.: The polyhedral state of molecular matter. Eur. J. Inorg. Chem. 7, 1571–1581 (2002) · doi:10.1002/1099-0682(200207)2002:7<1571::AID-EJIC1571>3.0.CO;2-X
[5] Lijnen E., Ceulemans A.: Oriented 2-cell embeddings of a graph and their symmetry classification: generating algorithms and case study of the Möbius-Kantor graph. J. Chem. Inf. Comput. Sci. 44, 1552–1564 (2004)
[6] Edmonds J.: A combinatorial representation for polyhedral surfaces. Am. Math. Soc. Not. 7, 646 (1960)
[7] In Ref. 5 we describe how the original topological map can be retrieved from a rotation scheme by a procedure called face-tracking
[8] Lijnen E., Ceulemans A.: Topology-aided molecular design: the Platonic molecules of genera 0 to 3. J. Chem. Inf. Model. 45(6), 1719–1726 (2005) · doi:10.1021/ci0502496
[9] B.P. Mull, R.G. Rieper, A.T. White, Enumerating 2-cell imbeddings of connected graphs. Proc. Am. Math. Soc. 103, 321–330 (1988) · Zbl 0653.05028
[10] King R.B.: Negative curvature surfaces in chemical structures. J. Chem. Inf. Comput. Sci. 38, 180–188 (1998)
[11] Ceulemans A., Lijnen E., Ceulemans L.J., Fowler P.W.: The tetrakisoctahedral group of the Dyck graph and its molecular realization. Mol. Phys. 102, 1149–1163 (2004) · doi:10.1080/00268970410001728780
[12] Marušič D., Pisanski T.: Symmetries of hexagonal molecular graphs on the torus. Croat. Chem. Acta 73, 969–981 (2000)
[13] Kutnar K., Malnič A., Marušič D.: Chirality of toroidal molecular graphs. J. Chem. Inf. Model. 45, 1527–1535 (2005) · doi:10.1021/ci050211t
[14] McMullen P., Schulte E.: Abstract Regular Polytopes. Cambridge University Press, Cambridge (2002) · Zbl 1039.52011
[15] E. Lijnen, A. Ceulemans, The symmetry of the Dyck graph: group structure and molecular realization. in Nanostructures: Novel Architecture, ed. by M. Diudea (Nova Publishers, New York, 2005) · Zbl 1187.92085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.