Complete forcing numbers of hexagonal systems (Q2046284)

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 \textit{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 \textit{matching number} of \(G\). A \textit{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 \textit{frame} of \(C\). Let \(M\) be a perfect matching of a graph \(G\). A \textit{forcing set} of \(M\) is a subset of \(M\) contained in no other perfect matching of \(G\). A \textit{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 \textit{minimum complete forcing set} of \(G\), and its cardinality is called the \textit{complete forcing number} of \(G\). This number is denoted as \(cf(G)\). A \textit{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 \textit{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 \textit{fixed double edge}; if \(e\) is not contained in any perfect matching of \(H\), then \(e\) is a \textit{fixed single edge}. In each of the previous cases, \(e\) is called a \textit{fixed edge}. Then \(H\) is a \textit{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. \noindent \textbf{Corollary.} \textit{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. \noindent \textbf{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. \noindent \textbf{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.