Cubic polyhedral Ramanujan graphs with face size no larger than six

A k-regular graph is Ramanujan if its second largest eigenvalue (by magnitude) has magnitude less than or equal to \({2\sqrt{k-1}}\). Exhaustive search up to the bound of 138 vertices, derived from Spielman and Teng’s work on graph partitioning, finds all cubic polyhedral Ramanujan graphs with positive curvature, i.e., with face sizes no larger than 6. Of all such polyhedra, those with face sizes 5 or 6, i.e., fullerenes, give the largest known examples of cubic Ramanujan polyhedra (with 84 vertices). We also consider the notions of negative and positive Ramanujan graphs, as those without eigenvalues in the respective open intervals \({(-k,-2\sqrt{k-1})}\) and \({(2\sqrt{k-1},k)}\). Our results give the full list of positive cubic polyhedral Ramanujan graphs with positive curvature but for negative Ramanujan graphs we have only a finiteness theorem and a conjectured complete list.     

Addition patterns in carbon allotropes: independence numbers and d-codes in the Klein and related graphs

The problem of predicting stoichiometries and patterns of chemical addition to a carbon framework, subject solely to the restriction that each addend excludes neighboring sites up to some distance d, is equivalent to determination of d-codes of a graph, and for d = 2 to determination of maximum independent sets. Sizes, symmetries, and numbers of d-codes are found for the all-heptagon Klein graph (prototype for "plumber's nightmare" carbon) and for three related graphs. The independence number of the Klein graph is 23, which increases to 24 for a related, but sterically relaxed, all-heptagon network with the same number of vertices and modified adjacencies. Expansion of the Klein graph and its relaxed analogue by insertion of hexagonal faces to form leapfrog graphs also allows all heptagons to achieve their maximum of 3 addends. Consideration of the pi system that is the complement of the addition pattern imposes a closed-shell requirement on the adjacency spectrum, which typically reduces the size of acceptable independent sets. The closed-shell independence numbers of the Klein graph and its relaxed analogue are 18 and 20, respectively.     

Hamilton cycles and paths in fullerenes

It has been conjectured that every fullerene, that is, every skeleton of a spherical trivalent graph whose set of faces consists of pentagons and hexagons alone, is Hamiltonian. In this article the validity of this conjecture is explored for the class of leapfrog-fullerenes. It is shown that, given an arbitrary fullerene F, the corresponding leapfrog-fullerene Le(F) contains a Hamilton cycle if the number of vertices of F is congruent to 2 modulo 4 and contains a long cycle missing out only two adjacent vertices, and thus also a Hamilton path, if the number of vertices of F is divisible by 4.     

Fullerenes as tilings of surfaces

If a fullerene is defined as a finite trivalent graph made up solely of pentagons and hexagons, embedding in only four surfaces is possible: the sphere, torus, Klein bottle, and projective (elliptic) plane. The usual spherical fullerenes have 12 pentagons; elliptic fullerenes, 6; and toroidal and Klein-bottle fullerenes, none. Klein-bottle and elliptic fullerenes are the antipodal quotients of centrosymmetric toroidal and spherical fullerenes, respectively. Extensions to infinite systems (plane fullerenes, cylindrical fullerenes, and space fullerenes) are indicated. Eigenvalue spectra of all four classes of finite fullerenes, are reviewed. Leapfrog fullerenes have equal numbers of positive and negative eigenvalues, with 0, 0, 2, or 4 eigenvalues zero for spherical, elliptic, Klein-bottle, and toroidal cases, respectively.     

Zigzags, railroads, and knots in fullerenes

Two connections between fullerene structures and alternating knots are established. Knots may appear in two ways: from zigzags, i.e., circuits (possibly self-intersecting) of edges running alternately left and right at successive vertices, and from railroads, i.e., circuits (possibly self-intersecting) of edge-sharing hexagonal faces, such that the shared edges occur in opposite pairs. A z-knot fullerene has only a single zigzag, doubly covering all edges: in the range investigated (n /= 38, all chiral, belonging to groups C(1), C(2), C(3), D(3), or D(5). An r-knot fullerene has a railroad corresponding to the projection of a nontrivial knot: examples are found for C(52) (trefoil), C(54) (figure-of-eight or Flemish knot), and, with isolated pentagons, at C(96), C(104), C(108), C(112), C(114). Statistics on the occurrence of z-knots and of z-vectors of various kinds, z-uniform, z-transitive, and z-balanced, are presented for trivalent polyhedra, general fullerenes, and isolated-pentagon fullerenes, along with examples with self-intersecting railroads and r-knots. In a subset of z-knot fullerenes, so-called minimal knots, the unique zigzag defines a specific Kekulé structure in which double bonds lie on lines of longitude and single bonds on lines of latitude of the approximate sphere defined by the polyhedron vertices.     

Version of zones and zigzag structure in icosahedral fullerenes and icosadeltahedra

A circuit of faces in a polyhedron is called a zone if each face is attached to its two neighbors by opposite edges. (For odd-sized faces, each edge has a left and a right opposite partner.) Zones are called alternating if, when odd faces (if any) are encountered, left and right opposite edges are chosen alternately. Zigzag (Petrie) circuits in cubic (= trivalent) polyhedra correspond to alternating zones in their deltahedral duals. With these definitions, a full analysis of the zone and zigzag structure is made for icosahedral centrosymmetric fullerenes and their duals. The zone structure provides hypercube embeddings of these classes of polyhedra which preserve all graph distances (subject to a scale factor of 2) up to a limit that depends on the vertex count. These embeddings may have applications in nomenclature, atom/vertex numbering schemes, and in calculation of distance invariants for this subclass of highly symmetric fullerenes and their deltahedral duals.     

Fullerene Graphs with Exponentially Many Perfect Matchings

We show that for all sufficiently large even p there is a fullerene graph on p vertices that has exponentially many perfect matchings in terms of the number of vertices. Further, we show that all fullerenes with full icosahedral symmetry group have exponentially many perfect matchings and indicate how such results could be extended to the fullerenes with lower symmetry.     

Symmetry factoring of the characteristic equations of graphs corresponding to polyhedra

A systematic procedure is described which uses two-and three-fold symmetry elements in graphs to reduce their adjacency matrices to lead to corresponding factorings of their characteristic polynomials. A graph splitting algorithm based on this matrix reduction procedure is described. Applications of these methods to the factoring of the characteristic polynomials of 28 polyhedra with nine or less vertices are given. General expressions for the eigenvalues of prisms, pyramids, and bipyramids in terms of the eigenvalues of their basal or equatorial regular polygons are calculated by closely related matrix methods.     

Cyclic 7-edge-cuts in fullerene graphs

A fullerene graph is a planar cubic graph whose all faces are pentagonal and hexagonal. The structure of cyclic edge-cuts of fullerene graphs of sizes at most 6 is known. In the paper we study cyclic 7-edge connectivity of fullerene graphs, distinguishing between degenerate and non-degenerate cyclic edge-cuts, regarding the arrangement of the 12 pentagons. We prove that if there exists a non-degenerate cyclic 7-edge-cut in a fullerene graph, then the graph is a nanotube unless it is one of the two exceptions presented. We determined that there are 57 configurations of degenerate cyclic 7-edge-cuts, and we listed all of them.     

Non-IPR fullerenes with properly closed shells

Fullerenes with properly closed shells (having exactly half their adjacency eigenvalues strictly positive) are rare. All reported examples obey the isolated-pentagon rule (IPR), usually considered a necessary condition of overall stability, and fall into three series (leapfrogs, carbon cylinders and sporadic closed shells). It is shown here that there also exist fullerenes with properly closed shells that violate the IPR ('super-sporadic' fullerenes). All have negative LUMO eigenvalues of small magnitude. Exhaustive search finds four examples with 160 or fewer vertices: one isomer of C(120), two of C(156) and one of C(160). The first three contain single pentagon pairs and the fourth, a linear triple of fused pentagons. Larger examples can be found. A capping construction gives a series of properly closed shell fullerenes of C(3)/C(3v) symmetry, each with a single fully fused triple of pentagons and ≥632 vertices. Tubular extension of the C(120) example leads a series of C(1)/C(s) isomer pairs with ≥168 vertices, retaining the single pentagon adjacency and approaching isospectrality with increasing size. Both constructions are conjectured to lead to an infinite number of super-sporadic fullerenes.     

Computer program for finding all possible cycles in graphs

A new approach is presented for identifying all possible cycles in graphs. Input data are the total numbers of vertices and edges, as well as the vertex adjacencies using arbitrary vertex numbering. A homeomorphically reduced graph (HRG) is constructed by ignoring vertices of degree less than three. The algorithm is based on successive generation of possible edge-combinations in the HRG. If a combination yields a cycle, it is either printed or stored and then finally printed in a list of all possible cycles arranged in the order of increasing ring size. A unique numbering of the cycle is used. The computer program is listed and exemplified. Computing times are given.     

On the enumeration of phase diagrams

The topological isomorphism of polyhedra with trivalent vertices and solid-liquid diagrams of three-component systems allows the problem of constructing the complete set of the topological types of diagrams with a given set of characteristics to be reduced to the problem of the generation of marked cubic graphs, which are the Schlegel projections of polyhedra. The problem of the enumeration of possible topological types of melting diagrams containing M binary and N ternary stoichiometric congruently melting compounds is considered. Relations between the topological characteristics of such diagrams are given. The total number of topologically different types of melting diagrams with one binary and one ternary congruently melting compounds was found to be 64.     

An Upper Bound for the Clar Number of Fullerene Graphs

A fullerene graph is a three-regular and three-connected plane graph exactly 12 faces of which are pentagons and the remaining faces are hexagons. Let F _n be a fullerene graph with n vertices. The Clar number c(F _n ) of F _n is the maximum size of sextet patterns, the sets of disjoint hexagons which are all M-alternating for a perfect matching (or Kekulé structure) M of F _n . A sharp upper bound of Clar number for any fullerene graphs is obtained in this article: . Two famous members of fullerenes C₆₀ (Buckministerfullerene) and C₇₀ achieve this upper bound. There exist infinitely many fullerene graphs achieving this upper bound among zigzag and armchair carbon nanotubes.     

The Chirality of Icosahedral Fullerenes: a Comparison of the Tripling (leapfrog), Quadrupling (chamfering), and Septupling (capra) Transformations

Fullerene polyhedra of icosahedral symmetry have the midpoints of their 12 pentagonal faces at the vertices of a macroicosahedron and can be characterized by the patterns of their hexagonal faces on the (triangular) macrofaces of this macroicosahedron. The numbers of the vertices in fullerene polyhedra of icosahedral symmetry satisfy the Goldberg equation v=20(h ²+hk+k ²), where h and k are two integers and 0 <h≥ k≥ 0 and define a two-dimensional Goldberg vector G = (h, k). The known tripling (leapfrog), quadrupling (chamfering), and septupling (capra) transformations correspond to the Goldberg vectors (1, 1), (2, 0), and (2, 1), respectively. The tripling and quadrupling transformations applied to the regular dodecahedron generate achiral fullerene polyhedra with the full I _h point group. However, the septupling transformation destroys the reflection operations of the underlying icosahedron to generate chiral fullerene polyhedra having only the I icosahedral rotational point group. Generalization of the quadrupling transformation leads to the fundamental homologous series of achiral fullerene polyhedra having 20 n ² vertices and Goldberg vectors (n, 0). A related homologous series of likewise achiral fullerene polyhedra having 60 n ² vertices and Goldberg vectors (n, n) is obtained by applying the tripling transformation to regular dodecahedral C₂₀ to give truncated icosahedral C₆₀ followed by the generalized operations (as in the case of quadrupling) for obtaining homologous series of fullerenes. Generalization of the septupling (capra) transformation leads to a homologous series of chiral C_20m fullerenes with the I point group and Goldberg vectors G=(h, 1) where m=h ²+h+1.     

Long cycles in fullerene graphs

It is conjectured that every fullerene graph is hamiltonian. Jendrol’ and Owens proved [J. Math. Chem. 18 (1995), pp. 83–90] that every fullerene graph on n vertices has a cycle of length at least 4n/5. In this paper we, improve this bound to 5n/6 − 2/3.     

New Lower Bound on the Number of Perfect Matchings in Fullerene Graphs

A fullerene graph is a cubic and 3-connected plane graph (or spherical map) that has exactly 12 faces of size 5 and other faces of size 6, which can be regarded as the molecular graph of a fullerene. T. Doli [3] obtained that a fullerene graph with p vertices has at least (p+2)/2 perfect matchings by applying the recently developed decomposition techniques in matching theory of graphs. This note gets a better lower bound 3(p+2)/4 of the number of perfect matchings of a fullerene graph by finding its 2-extendability. This property further implies a chemical consequence that every derivative of a fullerene by substituting any two pairs of adjacent carbon atoms permits a Kekulé structure.     

On discerning symmetry properties of graphs

A procedure is outlined which allows the symmetry properties of graphs to be systematically and rigorously investigated. It is based on a search for all the automorphisms of a graph and this is accompanied by suitably applying the procedure for recognizing identical graphs. It consists in finding all the distinctive labeling of the vertices of graph associated with the smallest binary code derived by a particular interpretation of the associated adjacency matrix. No prior cognizance of symmetry operations is required which is in contrast to the usual discussions of the symmetry properties of molecules which are based on the knowledge of pertinent symmetry operations. This is important since in graphs it is neither apparent nor generally possible to simply enlist those permutations of labels which leave the connectivity invariant (i.e., do not alter the form of the adjacency matrix). The procedure is applied to the Petersen graphs and the Desargues-Levi graph, both associated with isomerizations of trigonal bipyramidal complex and other chemical transformations. It is shown that these graphs of high symmetry belong to symmetry groups of order 120 and 240 respectively. The approach can also provide a basis for the development of the symmetry properties of non-rigid molecules in which connectivity is preserved.     

On lower bounds of number of perfect matchings in fullerene graphs

Couting perfect matchings in graphs is a very difficult problem. Some recently developed decomposition techniques allowed us to estimate the lower bound of the number of perfect matchings in certain classes of graphs. By applying these techniques, it will be shown that every fullerene graph with p vertices contains at least p/2+1 perfect matchings. It is a significant improvement over a previously published estimate, which claimed at least three perfect matchings in every fullerene graph. As an interesting chemical consequence, it is noted that every bisubstituted derivative of a fullerene still permits a Kekulé structure.     

Algorithm for topological correction of lists of simplexes of different dimensions for polyhedration of multicomponent systems

A new algorithm for polyhedration of quaternary and quaternary reciprocal systems is presented. The algorithm is based on checking all the links between vertices of a graph describing the composition diagram and selecting the polyhedration variants that correspond to the relations between the numbers of geometric elements of the complex undergoing polyhedration (graph vertices, links between them, and two-and three-dimensional complexes). Unlike Kraeva’s algorithm based on the decomposition of the graph in terms of zero elements of the adjacency matrix (absent links between vertices), the new algorithm can control the entire polyhedration process, accelerates the search for internal diagonals in the polyhedron, and takes into account their possible competition.