Original scientific paper

https://doi.org/10.5562/cca3099

A Dual of the Cycle Theorem and its Application to Molecular Complexity

Edward C. Kirby ; Resource Use Institute, Fishersview Court, Pitlochry PH16 5AN, Scotland, United Kingdom
Roger B. Mallion ; School of Physical Sciences, University of Kent, Canterbury CT2 7NH, England, United Kingdom
Paul Pollak ; The King’s School, Canterbury CT1 2ES, England, United Kingdom
Paweł J. Skrzyński ; The Canterbury High School, Canterbury CT2 8QA, England, United Kingdom

Abstract

The duality alluded to in the title is that between the faces and vertices of a graph embedded on a surface. Its recognition in the context of the five Platonic solids is classic. Algebraically, it is present in the equation for Euler’s Polyhedron Theorem and in the various extensions thereof. The Cycle Theorem (CT) establishes a formula for the number of spanning trees contained in a graph embedded on a surface. It is based on the mutual incidences of its cycles (circuits which also carry a sense of direction), i.e., of sub-graphs of the Cn type, endorsed with a sense. These appear (though not exclusively) as the boundaries of faces, so that, so to speak, the Cycle Theorem establishes a result which is essentially about vertices via relations between faces. Among several possible duals of the Cycle Theorem there might thus be one that estab¬lishes a relation which is essentially about faces via relations between vertices. In order to formulate one, we define, for an embedded graph, a feature concerning faces that is dual to a spanning tree. We call it a ladder. A formula is presented for the number of ladders contained in a graph which, in some cases, introduces the concept of ‘artificial vertices’. It is based on the mutual incidences of its vertices. Its form is clearly analogous, or ‘dual’, to the Cycle Theorem formula for spanning trees, previously proposed (in this journal — 2004) by three of the present authors, together with Klein and Sachs. A new index is proposed, which involves ladders. We call it the Patency Index of a graph; its numerical value may be related to molecular complexity. It is effectively the dual of, and is entirely analogous to, the Spanning-Tree Density Index which was earlier (2003) proposed, defined and applied to molecular graphs by one of the present authors and Trinajstić.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Keywords

Chemical graph theory; duality; molecular complexity; spanning trees; ladders; Cycle Theorem

Hrčak ID:

183712

URI

https://hrcak.srce.hr/183712

Publication date:

2.1.2017.

Visits: 1.713 *