×

Complete forcing numbers of hexagonal systems. (English) Zbl 1478.92262

In this paper, the authors present some bounds for the complete forcing number of hexagonal systems and deduce closed formulas for particular types of these graphs. To state the main results, we need to introduce some definitions from the paper.
A matching of a graph \(G\) is a set of disjoint edges of \(G\). The cardinality of a maximum matching of \(G\), denoted by \(\nu(G)\), is called the matching number of \(G\). A perfect matching of \(G\) is a matching \(M\) of \(G\) such that every vertex of \(G\) is an end vertex of some edge in \(M\). For an even cycle \(C\), each of the two perfect matchings of \(C\) is called a frame of \(C\).
Let \(M\) be a perfect matching of a graph \(G\). A forcing set of \(M\) is a subset of \(M\) contained in no other perfect matching of \(G\). A complete forcing set of \(G\) is a subset of \(E(G)\) to which the restriction of each perfect matching \(M\) is a forcing set of \(M\). A complete forcing set with the minimum cardinality is called a minimum complete forcing set of \(G\), and its cardinality is called the complete forcing number of \(G\). This number is denoted as \(cf(G)\).
A hexagonal system (HS) is a 2-connected finite plane graph such that every interior face is a regular hexagon. An HS in which all vertices belong to the outer face is called catacondensed.
Let \(H\) be an HS with a perfect matching and \(e \in E(H)\). If \(e\) is contained in all perfect matchings of \(H\), then \(e\) is a fixed double edge; if \(e\) is not contained in any perfect matching of \(H\), then \(e\) is a fixed single edge. In each of the previous cases, \(e\) is called a fixed edge. Then \(H\) is a normal HS if \(H\) does not contain a fixed edge.
In Section 2 of the paper, authors first show that it is important to determine the complete forcing number of normal HSs, since the \(cf(H)\) can be computed as the sum of complete forcing numbers of so-called normal components of \(H\). Next, an upper bound for the complete forcing number of a \(HS\) with a perfect matching is established. In particular, the complete forcing set of \(H\) is constructed by using so-called e-cuts. As a consequence of this theorem, the following result is obtained.
Corollary. Let \(H\) be an HS and \(S\) be the set consisting of all parallel edges with the minimum cardinality among three edge directions. Then \(cf(H) \leq |S|\).
Next, in Section 3, two lower bounds on the complete forcing number are proved.
Theorem. Let \(H\) be a normal HS with \(n\) hexagons. Then \(cf(H) \geq n + 1\).
For the second lower bound, the authors partition the set \(E(H)\) into several classes. For \(e', e'' \in E(H)\) , \(e'\) and \(e''\) belong to the same class if there is a sequence of hexagons \(h_1, h_2, \ldots, h_t\) and a sequence of edges \(e_1,e_2,\ldots, e_{t-1}\) of \(H\) such that \(e_{i-1}\) and \(e_i\) belong to the same frame of \(h_i\) for \(i \in \lbrace 1, \ldots, t \rbrace\), where \(e_0 = e'\) and \(e_t = e''\). Otherwise, \(e'\) and \(e''\) belong to different classes. We denote by \(E_1, E_2,\ldots, E_k\) all the classes obtained by this partition. Moreover, let \(\mathcal{H}_i\) be the set of hexagons of \(H\) that contain a frame in \(E_i\) and let \(H_i^{\sharp}\) be the subgraph of the dual graph \(H^*\) induced by the vertices corresponding to the hexagons of \(\mathcal{H}_i\), where \(i \in \lbrace 1, \ldots, k\rbrace\).
We can now state the second lower bound.
Theorem. Let \(H\) be a normal HS with \(n\) hexagons. Then \[cf(H) \geq 2n - \sum_{i=1}^k \nu (H_i^{\sharp}).\] It should be noted that the equality in the last theorem holds for all catacondensed HS.
In the final section of the paper, the authors deduce closed formulas for the complete forcing number of parallelogram HS, regular hexagon-shaped HS, and rectangle-shaped HS. In particular, they construct a complete forcing set whose cardinality is the same as the lower bound in one of the previous theorems.

MSC:

92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
05C92 Chemical graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abeledo, H.; Atkinson, GW, A min-max theorem for plane bipartite graphs, Discrete Appl. Math., 158, 375-378 (2010) · Zbl 1225.05197 · doi:10.1016/j.dam.2009.11.004
[2] Bondy, JA; Murty, USR, Graph Theory with Applications (1976), New York, Macmillan, London: American Elsevier, New York, Macmillan, London · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[3] Balaban, AT; Randić, M., Coding canonical Clar structures of polycyclic benzenoid hydrocarbons, MATCH Commun. Math. Comput. Chem., 82, 139-162 (2019) · Zbl 1472.92276
[4] Che, Z.; Chen, Z., Forcing on perfect matchings-A survey, MATCH Commun. Math. Comput. Chem., 66, 93-136 (2011) · Zbl 1265.05001
[5] Clar, E., The Aromatic Sextet (1972), London: Wiley, London
[6] Cyvin, SJ; Gutman, I., Kekulé Structures in Benzenoid Hydrocarbons (1988), Berlin: Springer, Berlin · doi:10.1007/978-3-662-00892-8
[7] Cai, J.; Zhang, H., Global forcing number of some chemical graphs, MATCH Commun. Math. Comput. Chem., 67, 289-312 (2012) · Zbl 1289.05370
[8] Chan, W.; Xu, S.; Nong, G., A linear-time algorithm for computing the complete forcing number and the Clar number of catacondensed hexagonal systems, MATCH Commun. Math. Comput. Chem., 74, 201-216 (2015) · Zbl 1462.05292
[9] Došlić, T., Global forcing number of benzenoid graphs, J. Math. Chem., 41, 217-229 (2007) · Zbl 1122.05089 · doi:10.1007/s10910-006-9056-2
[10] Gutman, I.; Cyvin, SJ, Introduction to the Theory of Benzenoid Hydrocarbons (1989), Berlin: Springer, Berlin · doi:10.1007/978-3-642-87143-6
[11] Herndon, WC, Resonance theory and the enumeration of Kekulé structures, J. Chem. Educ., 51, 10-15 (1974) · doi:10.1021/ed051p10
[12] Harary, F.; Klein, DJ; Živković, TP, Graphical properties of polyhexes: perfect matching vector and forcing, J. Math. Chem., 6, 295-306 (1991) · doi:10.1007/BF01192587
[13] Hansen, P.; Zheng, M., Upper bounds for the Clar number of benzenoid hydrocarbons, J. Chem. Soc. Faraday Trans., 88, 1621-1625 (1992) · doi:10.1039/ft9928801621
[14] Hansen, P.; Zheng, M., Normal components of benzenoid systems, Theor. Chim. Acta, 85, 335-344 (1993) · doi:10.1007/BF01113427
[15] Hansen, P.; Zheng, M., The Clar number of a benzenoid hydrocarbon and linear programming, J. Math. Chem., 15, 93-107 (1994) · doi:10.1007/BF01277551
[16] Klein, DJ; Randić, M., Innate degree of freedom of a graph, J. Comput. Chem., 8, 516-521 (1987) · doi:10.1002/jcc.540080432
[17] Liu, B.; Bian, H.; Yu, H., Complete forcing numbers of polyphenyl systems, Iran. J. Math. Chem., 7, 39-46 (2016) · Zbl 1406.92770
[18] Liu, B.; Bian, H.; Yu, H.; Li, J., Complete forcing number of spiro hexagonal systems, Polyc. Arom. Comp. (2019) · doi:10.1080/10406638.2019.1600560
[19] Lovász, L.; Plummer, MD, Matching Theory, Annals of Discrete Mathematics (1986), Amsterdam: North-Holland, Amsterdam · Zbl 0618.05001
[20] Langner, J.; Witek, HA, Interface theory of benzenoids, MATCH Commun. Math. Comput. Chem., 84, 143-176 (2020) · Zbl 1473.92077
[21] Langner, J.; Witek, HA, Interface theory of benzenoids: Basic applications, MATCH Commun. Math. Comput. Chem., 84, 177-215 (2020) · Zbl 1473.92078
[22] Mahmoodian, ES; Naserasr, R.; Zaker, M., Defining sets in vertex colorings of graphs and Latin rectangles, Discrete Math., 167, 451-460 (1997) · Zbl 0879.05028 · doi:10.1016/S0012-365X(96)00247-6
[23] Sachs, H., Perfect matchings in hexagonal system, Combinatorica, 4, 89-99 (1984) · Zbl 0542.05048 · doi:10.1007/BF02579161
[24] Sedlar, J., The global forcing number of the parallelogram polyhex, Discrete Appl. Math., 160, 2306-2313 (2012) · Zbl 1252.05180 · doi:10.1016/j.dam.2012.05.021
[25] Vukičević, D.; Došlić, T., Global forcing number of grid graphs, Aust. J. Combin., 38, 47-62 (2007) · Zbl 1143.05043
[26] Vukičević, D.; Sedlar, J., Total forcing number of the triangular grid, Math. Commun., 9, 169-179 (2004) · Zbl 1063.05074
[27] Xu, S.; Liu, X.; Chan, W., H, Zhang, Complete forcing numbers of primitive coronoids, J. Comb. Opt., 32, 318-330 (2016) · Zbl 1354.90119 · doi:10.1007/s10878-015-9881-y
[28] Xu, S.; Zhang, H.; Cai, J., Complete forcing numbers of catacondensed hexagonal systems, J. Comb. Opt., 29, 803-814 (2015) · Zbl 1321.90148 · doi:10.1007/s10878-013-9624-x
[29] Zhang, F.; Chen, R., When each hexagon of a hexagonal system covers it, Discrete Appl. Math., 30, 63-75 (1991) · Zbl 0763.05087 · doi:10.1016/0166-218X(91)90014-N
[30] Zhang, F.; Chen, R.; Guo, X., Perfect matchings in hexagonal systems, Graphs Combin., 1, 383-386 (1985) · Zbl 0614.05043 · doi:10.1007/BF02582965
[31] Zhang, H.; Cai, J., On the global forcing number of hexagonal systems, Discrete Appl. Math., 162, 334-347 (2014) · Zbl 1300.05265 · doi:10.1016/j.dam.2013.08.020
[32] Zhang, H.; Zhang, F., The Clar covering polynomial of hexagonal systems I, Discrete Appl. Math., 69, 147-167 (1996) · Zbl 0859.05070 · doi:10.1016/0166-218X(95)00081-2
[33] Zhang, H.; Yao, H.; Yang, D., A min-max result on outerplane bipartite graphs, Appl. Math. Lett., 20, 199-205 (2007) · Zbl 1109.05101 · doi:10.1016/j.aml.2006.03.014
[34] Zhang, H.; Zhang, F., Plane elementary bipartite graphs, Discrete Appl. Math., 105, 473-490 (2000) · Zbl 0957.05085 · doi:10.1016/S0166-218X(00)00204-3
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.