The enumeration of several classes of hexagonal systems

Ahexagonalsystemisafiniteconnectedplanegraphwithnocutvertexinwhicheveryinteriorfaceisboundedbyaregularhexagonofsidelengthone.AhexagonalsystemHissaidtobeacata-condensedhexagonalsystemifeaChvertexofHisontheboundaryofH;otherwise,apert-condensedhexagonalsystem.Chemistsusuallycallthembenzenoidsystems,andsomemathematicianscallthempolyhexgraphs.Chemistsareillterestedinthistakeofgraphsandtheenumerationofthemsincetheyrepreselltthecarbonatomskeletongraphsofbenzenoidhydrocarbons[2--31.Ontheotherhand,th…     

Perfect matchings in hexagonal systems

A simple algorithm is developed which allows to decide whether or not a given hexagonal system has a perfect matching (and to find such a matching). This decision is also of chemical relevance since a hexagonal system is the skeleton of a benzenoid hydrocarbon molecule if and only if it has a perfect matching. Dedicated to Paul Erdős on his seventieth birthday     

渺位六角系统完美匹配Z——变换图

六角系统是2-连通的平面图，其每个内部面都是单位正六边形．六角系统的完美匹配是化学中苯类芳烃体系的Kekule结构．一个六角系统H完美匹配Z—变换图Z（H）是一个图，它的顶点集是H的完匹配集，两个匹配相邻当且仅当它们的对称差是一个单位正六边形．本文用乘积图刻划了沙位六角系统Z—变换图的结构．     

Hexagonal systems with forcing edges

An edge of a hexagonal system H is said to be forcing if it belongs to exactly one perfect matching of H. Using the concept of Z-transformation of hexagonal system, we give a characterization for the hexagonal systems with forcing edges and determine all forcing edges is such systems. We also give the generating function of all hexagonal systems with forcing edges.     

Existence of perfect matchings in a plane bipartite graph

We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the paper of F. Zhang, R. Chen and X. Guo (1985).     

A theorem concerning perfect matchings in hexagonal systems

In the present paper a theorem is established which offers some necessary and sufficient conditions for a hexagonal system to have perfect matchings.The project supported by National Natural Science Foundation of China.     

Anti-forcing spectrum of any cata-condensed hexagonal system is continuous

The anti-forcing number of a perfect matching M of a graph G is the minimal number of edges not in M whose removal makes M a unique perfect matching of the resulting graph. The anti-forcing spectrum of G is the set of anti-forcing numbers over all perfect matchings of G: In this paper, we prove that the anti-forcing spectrum of any cata-condensed hexagonal system is continuous, that is, it is a finite set of consecutive integers.     

On periodicity of perfect colorings of the infinite hexagonal and triangular grids

A coloring of vertices of a graph G is called r-perfect, if the color structure of each ball of radius r in G depends only on the color of the center of the ball. The parameters of a perfect coloring are given by the matrix A = (a _ij ) _i,j=1 ⁿ , where n is the number of colors and a _ij is the number of vertices of color j in a ball centered at a vertex of color i. We study the periodicity of perfect colorings of the graphs of the infinite hexagonal and triangular grids. We prove that for every 1-perfect coloring of the infinite triangular and every 1- and 2-perfect coloring of the infinite hexagonal grid there exists a periodic perfect coloring with the same matrix. The periodicity of perfect colorings of big radii have been studied earlier.     

Hypergraphs and the Clar problem in hexagonal systems

We show that for a hypergraph H that is separable and has the Helly property, the perfect matchings of H are the strongly stable sets of the line graph of H. Also, we show that the hypergraph generated by a hexagonal system is separable and has the Helly property. Finally, we note that the Clar problem of a hexagonal system is a minimum cardinality perfect matching problem of the hypergraph generated by the hexagonal system. Hence, the Clar problem of a hexagonal system is a minimum cardinality strongly stable set problem in the line graph of the hypergraph generated by the hexagonal system.     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

The connectivity ofZ-transformation graphs of perfect matchings of hexagonal systems

LetH be a hexagonal system. TheZ-transformation graphZ(H) is a graph where the vertices are perfect matchings ofH and where two perfect matchings are joined by an edge provided their synimetric difference consists of six edges of a hexagon ofH. We prove that the connectivity ofZ(H) is equal to the minimum degree of vertices ofZ(H).Project supported by the National Natural Science Foundation of China.     

2-extendability of toroidal polyhexes and Klein-bottle polyhexes

A toroidal polyhex (resp. Klein-bottle polyhex) described by a string (p,q,t) arises from a p×q-parallelogram of a hexagonal lattice by a usual torus (resp. Klein bottle) boundary identification with a torsion t. A connected graph G admitting a perfect matching is k-extendable if |V(G)|≥2k+2 and any k independent edges can be extended to a perfect matching of G. In this paper, we characterize 2-extendable toroidal polyhexes and 2-extendable Klein-bottle polyhexes.     

Forcing faces in plane bipartite graphs

Let Ω denote the class of connected plane bipartite graphs with no pendant edges. A finite face s of a graph G∈Ω is said to be a forcing face of G if the subgraph of G obtained by deleting all vertices of s together with their incident edges has exactly one perfect matching. This is a natural generalization of the concept of forcing hexagons in a hexagonal system introduced in Che and Chen [Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (3) (2006) 649-668]. We prove that any connected plane bipartite graph with a forcing face is elementary. We also show that for any integers n and k with n?4 and n?k?0, there exists a plane elementary bipartite graph such that exactly k of the n finite faces of G are forcing. We then give a shorter proof for a recent result that a connected cubic plane bipartite graph G has at least two disjoint M-resonant faces for any perfect matching M of G, which is a main theorem in the paper [S. Bau, M.A. Henning, Matching transformation graphs of cubic bipartite plane graphs, Discrete Math. 262 (2003) 27-36]. As a corollary, any connected cubic plane bipartite graph has no forcing faces. Using the tool of Z-transformation graphs developed by Zhang et al. [Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405-415; Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291-311], we characterize the plane elementary bipartite graphs whose finite faces are all forcing. We also obtain a necessary and sufficient condition for a finite face in a plane elementary bipartite graph to be forcing, which enables us to investigate the relationship between the existence of a forcing edge and the existence of a forcing face in a plane elementary bipartite graph, and find out that the former implies the latter but not vice versa. Moreover, we characterize the plane bipartite graphs that can be turned to have all finite faces forcing by subdivisions.     

Relations between Clar structures, Clar covers, and the sextet-rotation tree of a hexagonal system

Sextet rotations of the perfect matchings of a hexagonal system H are represented by the sextet-rotation-tree R(H), a directed tree with one root. In this article we find a one-to-one correspondence between the non-leaves of R(H) and the Clar covers of H, without alternating hexagons. Accordingly, the number (nl) of non-leaves of R(H) is not less than the number (cs) of Clar structures of H. We obtain some simple necessary and sufficient conditions, and a criterion for cs=nl, that are useful for the calculation of Clar polynomials. A procedure for constructing hexagonal systems with cs<nl is provided in terms of normal additions of hexagons.     

Die Sechseck-n-Waben in der Ebene,welche von n Kreisbüscheln erzeugt werden

In this paper, the problem of determining the pencils of circles which form a hexagonal n-web in E₂, is completely solved. It is well-known that n pencils of circles orthogonal to a fixed circle form a hexagonal n-web. Therefore, the main problem is the determination of all circle pencils which form a hexagonal n-web and which do not cut a fixed circle orthogonally. In this connection the following results have been obtained: The number of hexagonal 4-webs is six, whereas the number of hexagonal 5-webs is two.Finally, after having proved that the number of hexagonal 6-webs is one, it is shown that, for n7, there exist no circle pencils forming a hexagonal n-web without being orthogonal to a fixed circle.     

On the energy and spectral properties of the He matrix of hexagonal systems

The He matrix, put forward by He and He in 1989, is designed as a means for uniquely representing the structure of a hexagonal system (= benzenoid graph). Observing that the He matrix is just the adjacency matrix of a pertinently weighted inner dual of the respective hexagonal system, we establish a number of its spectral properties. Afterwards, we discuss the number of eigenvalues equal to zero of the He matrix of a hexagonal system. Moreover, we obtain a relation between the number of triangles and the eigenvalues of the He matrix of a hexagonal system. Finally, we present an upper bound on the He energy of hexagonal systems.     

Analysis solution method for 3D planar crack problems of two-dimensional hexagonal quasicrystals with thermal effects

An analysis solution method (ASM) is proposed for analyzing arbitrarily shaped planar cracks in two-dimensional (2D) hexagonal quasicrystal (QC) media. The extended displacement discontinuity (EDD) boundary integral equations governing three-dimensional (3D) crack problems are transferred to simplified integral-differential forms by introducing some complex quantities. The proposed ASM is based on the analogy between these EDD boundary equations for 3D planar cracks problems of 2D hexagonal QCs and those in isotropic thermoelastic materials. Mixed model crack problems under combined normal, tangential and thermal loadings are considered in 2D hexagonal QC media. By virtue of ASM, the solutions to 3D planar crack problems under various types of loadings for 2D hexagonal QCs are formulated through comparison to the corresponding solutions of isotropic thermoelastic materials which have been studied intensively and extensively. As an application, analytical solutions of a penny-shaped crack subjected uniform distributed combined loadings are obtained. Especially, the analytical solutions to a penny-shaped crack subjected to the anti-symmetric uniform thermal loading are first derived for 2D hexagonal QCs. Numerical solutions obtained by EDD boundary element method provide a way to verify the validity of the presented formulation. The influences of phonon-phason coupling effect on fracture parameters of 2D hexagonal QCs are assessed.     

Extremal double hexagonal chains with respect to k-matchings and k-independent sets

“Double hexagonal chains” can be considered as benzenoids constructed by successive fusions of successive naphthalenes along a zig-zag sequence of triples of edges as appear on opposite sides of each naphthalene unit. In this paper, we discuss the numbers of k-matchings and k-independent sets of double hexagonal chains, as well as Hosoya indices and Merrifield-Simmons indices, and obtain some extremal results: among all the double hexagonal chains with the same number of naphthalene units, (a) the double linear hexagonal chain has minimal k-matching number and maximal k-independent set number and (b) the double zig-zag hexagonal chain has maximal k-matching number and minimal k-independent set number, which are extensions to hexagonal chains [L. Zhang and F. Zhang, Extremal hexagonal chains concerning k-matchings and k-independent sets, J. Math. Chem. 27 (2000) 319-329].     

Glider-based computing in reaction-diffusion hexagonal cellular automata

A three-state hexagonal cellular automaton, discovered in [Wuensche A. Glider dynamics in 3-value hexagonal cellular automata: the beehive rule. Int J Unconvention Comput, in press], presents a conceptual discrete model of a reaction-diffusion system with inhibitor and activator reagents. The automaton model of reaction-diffusion exhibits mobile localized patterns (gliders) in its space–time dynamics. We show how to implement the basic computational operations with these mobile localizations, and thus demonstrate collision-based logical universality of the hexagonal reaction-diffusion cellular automaton.     

On well-rounded sublattices of the hexagonal lattice

We produce an explicit parameterization of well-rounded sublattices of the hexagonal lattice in the plane, splitting them into similarity classes. We use this parameterization to study the number, the greatest minimal norm, and the highest signal-to-noise ratio of well-rounded sublattices of the hexagonal lattice of a fixed index. This investigation parallels earlier work by Bernstein, Sloane, and Wright where similar questions were addressed on the space of all sublattices of the hexagonal lattice. Our restriction is motivated by the importance of well-rounded lattices for discrete optimization problems. Finally, we also discuss the existence of a natural combinatorial structure on the set of similarity classes of well-rounded sublattices of the hexagonal lattice, induced by the action of a certain matrix monoid.