Complete forcing numbers of primitive coronoids

Abstract

Let $G$ be a graph with edge set $E(G)$ that admits a perfect matching $M$. A forcing set of $M$ is a subset of $M$ contained in no other perfect matching of $G$. A complete forcing set of $G$, recently introduced by Xu et al. (J Combin Optim 29(4):803–814, 2015c), is a subset of $E(G)$ to which the restriction of any perfect matching is a forcing set of the perfect matching. The minimum possible cardinality of a complete forcing set of $G$ is the complete forcing number of $G$. Previously, Xu et al. (J Combin Optim 29(4):803–814, 2015c) gave an expression for the complete forcing number of a hexagonal chain and a recurrence relation for complete forcing numbers of catacondensed hexagonal systems. In this article, by the constructive proof, we give an explicit analytical expression for the complete forcing number of a primitive coronoid, a circular single chain consisting of congruent regular hexagons (i.e., Theorem 3.9).

1 Introduction

A perfect matching of a graph is a set of disjoint edges that covers all vertices of the graph. Perfect matchings arose in the dimer problem of statistical physics, as Kekulé structures of organic chemistry and in the personnel assignment problem of operations research (Lovász and Plummer 1986). The number of Kekulé structures (i.e., perfect matchings) of a benzenoid hydrocarbon can be used to measure its stability (Cyvin and Gutman 1988). The idea of “forcing” has long been used in many research fields in graph theory and combinatorics (Gray 1990; Mahmoodian et al. 1997), and its application to a perfect matching $M$ of a graph first appeared in Harary et al. (1991), that is, a subset $S$ of $M$ forces exactly one perfect matching of $G$, namely, $M$. In other words, if $S$ occurs simultaneously in no other perfect matching, such an $S$ is called a forcing set of $M$. The minimum possible cardinality of $S$ is called the forcing number of $M$. The forcing number can traceits origin back to the papers (Klein and Randić 1987; Randić and Klein 1985) by Randić and Klein in the chemical literature, where the forcing number was introduced under the name of “innate degree of freedom” of a Kekulé structure, which plays an important role in the resonance theory in chemistry. For more results on the forcing number, we refer the reader to Adams et al. (2004), Afshani et al. (2004), Kleinerman (2006), Lam and Pachter (2003), Pachter and Kim (1998), Riddle (2002), and Zhang et al. (2010).

Forcing sets and forcing numbers of perfect matchings of a graph $G$ with edge set $E(G)$ are defined by the “local” approach, i.e., defined with respect to a particular perfect matching of $G$. Vukičević and Došlić (2007), Vukičević and Sedlar (2004) introduced the concept of global (or total) forcing set from the “global” point of view, i.e., concerning all perfect matchings instead of a particular perfect matching, which is defined as a subset $S$ of $E(G)$ on which there are no two distinct perfect matchings coinciding, i.e., the restriction of the characteristic function of perfect matchings to $S$ is an injection. On the other hand, Klein and Randić (1987) proposed the degree of freedom of a graph from the “global” point of view, defined as the sum of forcing numbers over all perfect matchings of a graph. Again, combining the “forcing” and “global” ideas, Xu et al. (2015c) first proposed studying a structure concerning all perfect matchings instead of a particular perfect matching, namely a subset $S$ of $E(G)$ to which the restriction of every perfect matching is a forcing set of the perfect matching. Such an $S$ is called a complete forcing set of $G$. The minimum possible cardinality of a complete forcing set is called the complete forcing number of $G$. To a certain extent, the complete forcing number of a graph gives some sort of identification of the minimal amount of “information” required to specify forcing sets of perfect matchings of the graph. Also, they established some initial results about complete forcing sets and the complete forcing number of a graph, including a necessary and sufficient condition for an edge set to be a complete forcing set of a graph, and proving that a complete forcing set of a graph is also a global forcing set and the converse is not true by a counterexample. For further results on the field, see Chan et al. (2015), Xu et al. (2015a, (2015b, (2015c).

In this article, we discuss complete forcing sets and complete forcing numbers of another class of graphs: primitive coronoids, circular single chains consisting of congruent regular hexagons (see Fig. 3 for an example), and give an explicit analytical expression for the complete forcing set of a primitive coronoid.

The present paper is organized as follows. In the next section, we formally define complete forcing sets, the complete forcing number of a graph and primitive coronoids, along with other graph-theoretic terms relevant to our subject. In addition, we give a necessary and sufficient condition for a set to be a complete forcing set of a general graph given in Xu et al. (2015c). In Sect. 3, we prove an explicit formula for the complete forcing number of a primitive coronoid. In Sect. 4, we explore whether a special necessary and sufficient condition for a set to be a complete forcing set of catacondensed hexagonal systems is applicable for primitive coronoids. Unfortunately, it will be shown to be negative by giving a counterexample.

2 Mathematical preliminaries

All graphs in this paper are simple and connected and have perfect matchings. For all terms and notation used but not defined here we refer the reader to the textbook (Diestel 2000).

A hexagonal system (or benzenoid system, polyhex graph) is a connected graph without cut vertices embedded into the regular hexagonal lattice in the plane, and in which all internal faces are regular hexagons. Note that hexagonal systems are bipartite. A hexagonal system is catacondensed if there are no three hexagons sharing one common vertex, i.e., all vertices lie on the boundary of the non-hexagonal external face. A hexagonal chain is a catacondensed hexagonal system in which no hexagon is adjacent to three hexagons.

A coronoid (or coronoid system) $G$ can be obtained from a hexagonal system $B$ by deleting at least one interior vertex together with the incident edges, and/or at least one internal edge such that each remained edge belongs to at least one hexagon of $G$ and a unique non-hexagonal interior face emerges. A coronoid consisting of a circular single chain will presently be referred to as primitive, i.e., a primitive coronoid is a coronoid in which each hexagon shares exactly two non-adjacent edges with its neighbouring hexagons (see Fig. 3 for an example).

Let $G$ be a hexagonal chain or primitive coronoid. A hexagon $r$ of $G$ has one or two neighbouring hexagons. If $r$ has exactly one neighbouring hexagon, then it is said to be terminal. A hexagon $r$ being adjacent to exactly two other hexagons is a kink if $r$ possesses two adjacent vertices of degree 2, and $r$ is linear otherwise. Note that the number ($\geqslant$6) of kinks in a primitive coronoid is even. A hexagonal chain with no kinks is said to be linear. A segment is a maximal linear chain in $G$, including kinks and/or terminal hexagons at its end. A kink segment in $G$ is defined as a maximal subgraph in $G$ consisting completely of kinks. Note that in the case of a primitive coronoid $G$ with all hexagons being kinks, $G$ itself is a kink segment; in the other cases, a kink segment can be defined as a maximal hexagonal chain consisting completely of kinks in $G$. The length of a segment or kink segment $S$ is the number of hexagons in $S$.

Let $G$ be a primitive coronoid. We call the boundary of the non-hexagonal internal (resp. external) face internal boundary (resp. external boundary), denoted by $C_0(G)$ (resp. $C_1(G)$), of $G$. An edge $e$ of $G$ is internal if $e$ is on $C_0(G)$, is external if $e$ is on $C_1(G)$, is shared otherwise.

A primitive coronoid $G$ is called convex, if $G$ contains exactly six segments (or, equivalently, six kinks). If we denote by $l_1, l_2, \ldots , l_6$ the length of these segments in turn, then, for $1\leqslant i\leqslant 6$,

$$\begin{aligned} l_i+l_{i+1}=l_{i+3}+l_{i+4}. \end{aligned}$$

(1)

Here subscripts are treated as modulo 6.

For subsets $S_1, S_2$ of a set $S$, symmetric difference $S_1\oplus S_2$ of $S_1$ and $S_2$ is defined as the set consisting of elements belonging to exactly one of $S_1$ and $S_2$.

Let $G$ be a connected graph with a perfect matching. A subgraph $H$ of $G$ is nice if $G-V(H)$ has a perfect matching. Obviously, an even cycle $C$ of $G$ is nice if and only if $C$ is exactly the symmetric difference of some two perfect matchings $M_1$ and $M_2$ of $G$, i.e., $C=M_1\oplus M_2$; we call $M_1\cap C$ and $M_2\cap C$ two type-sets of the nice cycle $C$. Alternatively, each type-set of a nice cycle $C$ is a perfect matching of $C$. Let $G$ be a primitive coronoid with a hexagon $r$ ($r$ is necessarily nice, see Lemma 3.1 in the next theorem). If $r$ is a kink, then two shared edges of $r$ belong to one common type-set of $r$, while two shared edges of a linear hexagon $r$ belong to two distinct type-sets of $r$, respectively.

Let $G$ be a connected graph with edge set $E(G)$ and a perfect matching $M$. A forcing set of $M$ is a subset of $M$ contained in no other perfect matching of $G$. It follows from the definition that the empty set is a forcing set of $M$ if and only if $M$ is the unique perfect matching of $G$. A complete forcing set of $G$ is a subset of $E(G)$ to which, for any perfect matching $M$, the restriction of $M$ is a forcing set of $M$. Obviously, $E(G)$ is a trivial complete forcing set of $G$. The minimum possible cardinality of a complete forcing set of $G$ is the complete forcing number of $G$, denoted by $cf(G)$.

As an illustrative example, we consider $K_4$ shown in Fig. 1. It contains three different perfect matchings: $M_1=\{e_1, e_4\}$, $M_2=\{e_2, e_5\}$, $M_3=\{e_3, e_6\}$. It is easy to see that the restriction of every perfect matching $M$ on $S=\{e_1, e_2, e_3\}$ is a forcing set of $M$. Hence $S$ is a complete forcing set of $K_4$. Since every complete forcing set contains at least one edge of every perfect matching of $K_4$ and $\{M_1, M_2, M_3\}$ is a partition of the edge set of $K_4$, $S$ is a complete forcing set of minimum cardinality. Hence, $cf(K_4)=3$.

Fig. 1

A complete forcing set $\{e_1, e_2, e_3\}$ of minimum cardinality in $K_4$ is indicated by bold edges

We end this section with a necessary and sufficient condition for set $S$ to be a complete forcing set of a graph with a perfect matching, given in Xu et al. (2015c).

Theorem 2.1

Xu et al. (2015c) Let $G$ be a graph with edge set $E(G)$ and a perfect matching. $S\subseteq E(G)$ is a complete forcing set of $G$ if and only if, for any nice cycle $C$ in $G$, the intersection of $S$ and each type-set of $C$ is non-empty.

3 Complete forcing numbers of primitive coronoids

In this section we discuss the calculation of the complete forcing number of a primitive coronoid $G$ and give an explicit analytical expression for the complete forcing number of a primitive coronoid (i.e., Theorem 3.9). First, we give some results relating to nice cycles in $G$.

3.1 Some results relating to nice cycles in primitive coronoids

Lemma 3.1

Let $G$ be a primitive coronoid. Then every hexagon is nice.

Proof

Let $h$ be a hexagon of $G$. If $h$ is a kink and let $L_1$ and $L_2$ be the two segments containing $h$. We can match the remained vertices on $L_1$ and $L_2$ (except vertices on two shared edges with other hexagons) as Fig. 2. Since the subgraph of $G$ obtained from $G$ by deleting matched vertices and vertices of $h$ is exactly a hexagonal chain, $G-V(h)$ has a perfect matching. Hence $h$ is a nice hexagon. If $h$ is linear, then we can prove it in a similar way.

Corollary 3.2

Cyvin et al. (1991) Every primitive coronoid has a perfect matching.

Fig. 2

Illustration for the proof of Lemma 3.1

Lemma 3.3

Let $G$ be a primitive coronoid with the internal boundary $C_0(G)$ and the external boundary $C_1(G)$, let $H$ be a hexagonal chain in $G$. We denote by $l, k$ the number of linear hexagons, kinks of $G$ in $H$, respectively and by $k'$ kinks with two adjacent 2-degree vertices on $C_0(G)$ (resp. $C_1(G)$) of $G$ in $H$. Then the intersection of $H$ and $C_0(G)$ (resp. $C_1(G)$) is a path of length $2l+2k'+k$.

Proof

Obviously, the intersection of $H$ and $C_0(G)$ (resp. $C_1(G)$) is a path, say $P$. It is sufficient to prove that there are $2l+2k'+k+1$ vertices on $P$. We now count vertices on $P$. There are $l+2k'$ 2-degree vertices of $G$ with one for each linear hexagon and two for each kink with two adjacent 2-degree vertices on $C_0(G)$ (resp. $C_1(G)$), $(l+k-1)+2=l+k+1$ 3-degree vertices of $G$ with one for each pair of adjacent hexagons in $H$ and two for endpoints of $P$. So there are totally $(l+2k')+(l+k+1)=2l+2k'+k+1$ vertices on $P$. $\square$

Corollary 3.4

Let $G$ be a primitive coronoid with the internal boundary $C_0(G)$ and the external boundary $C_1(G)$, $H$ a hexagonal chain in $G$. The length of the path $P=H\cap C_0(G)$ (resp. $H\cap C_1(G)$) has the same parity as the number of kinks of $G$ in $H$.

Corollary 3.5

Let $G$ be a primitive coronoid with the internal boundary $C_0(G)$ and the external boundary $C_1(G)$, $H$ a hexagonal chain between two successive kinks inclusive in $G$. Then the length of the path $P=H\cap C_0(G)$ (resp. $H\cap C_1(G)$) is even.

In what follows, we give a necessary and sufficient condition for cycles of a special type in a primitive coronoid to be nice.

Theorem 3.6

Let $G$ be a primitive coronoid, $C$ a cycle containing the non-hexagonal internal face of $G$. Then $C$ is nice if and only if $C$ is either (i) the internal boundary $C_0(G)$ or the external boundary $C_1(G)$ or (ii) a cycle such that every hexagonal chain in $G$ divided by the shared edges of $C$ contain an odd number of kinks of $G$.

Proof

Necessity: Let $C$ be a nice cycle containing the non-hexagonal internal face of $G$. Then $G-V(C)$ consists of either one even cycle or the disjoint union of paths of odd length. For the former case $C$ corresponds to $C_0(G)$ or $C_1(G)$, while for the latter case $C$ corresponds to a cycle such that every hexagonal chain in $G$ divided by the shared edges of $C$ contains an odd number of kinks of $G$ by Corollary 3.4.

Sufficiency: If $C$ is $C_0(G)$ or $C_1(G)$, then $G-V(C)$ is an even cycle and further has a perfect matching. Hence $C$ is nice. If $C$ is a cycle satisfying the condition (ii), then $G-V(C)$ consists of the disjoint union of paths of odd length by Corollary 3.4, each of which has a perfect matching. So $C$ is nice. $\square$

Corollary 3.7

Let $G$ be a primitive coronoid, $C$ a nice cycle of $G$ containing the non-hexagonal internal face.

• (1) Then shared edges in $C$ belong to the same type-set of $C$;

• (2) Let $e_1, e_2$ two internal (resp. external) edges in $C$. If $e_1, e_2$ are in two successive kinks, say $K_1$ and $K_2$, respectively and the type set of $K_i$ containing $e_i$ does not contain any shared edge in $G$ for $i=1, 2$, then $e_1, e_2$ belong to two distinct type-sets of $C$, respectively.

Proof

• (1) It is sufficient to prove that two successive shared edges, say $e_1$ and $e_2$, in $C$ belong to one common type-set of $C$ and we can prove (1) by the transitivity. Let $P$ be a path in $C$ between $e_1$ and $e_2$ inclusive containing no other shared edges. By Theorem 3.6 (ii) and Corollary 3.4, $P$ has odd length. Hence $e_1, e_2$ belong to one common type-set of $C$.

• (2) It is sufficient to prove that the path, say $P$, between $e_1$ and $e_2$ inclusive in $C$ containing no edges of the other kinks has even length, which can be easily proven by Corollay 3.5.

$\square$

We give a theorem shown by Zhang and Zhang: Corollary 3.4 in Zhang and Zhang (2000), which is applicable to a wider range therein than we list below.

Theorem 3.8

Zhang and Zhang (2000) Let $G$ be a primitive coronoid, $C$ a nice cycle containing no non-hexagonal internal face. For any type-set $M(C)$ of $C$, there exists a hexagon, say $h$, contained in $C$ such that $M(C)\cap E(h)$ is one type-set of $h$.

3.2 Calculating complete forcing numbers of primitive coronoids

For the sake of simplicity, we denote by $k_i(G)$ ($k_i$ for short, if there is no confusion) the number of kink segments of length $i$ in a primitive coronoid $G$ with edge set $E(G)$, $i=1, 2, \ldots$. We give some conventions: Let $S, E'\subseteq E(G)$ with an edge $e\in E'$. If $e$ is not in $S$, then we say $E'$ contributes $0$ to $|S|$ in terms of $e$; if $e$ is in $S$ and shared, then we say $E'$ contributes $\frac{1}{2}$ to $|S|$ in terms of $e$; if $e$ is in $S$ and not shared, then we say $E'$ contributes $1$ to $|S|$ in terms of $e$. The contribution of $E'$ to $|S|$ is defined as the sum of contributions in terms of $e$ over all edges $e$ in $E'$. In the following the contribution of a hexagon $h$ to $|S|$ means the contribution of its edge set $E(h)$ to $|S|$. Hence the contribution of all hexagons to $|S|$ is exactly $|S|$. We now give our main result: an explicit formula for the complete forcing number of a primitive coronoid $G$ with $n$ hexagons in terms of $n$ and all $k_i(G)$.

Theorem 3.9

Let $G$ be a primitive coronoid with $n$ hexagons ($n$ must be even), $k_i$ the number of kink segments in $G$ of length $i$ for $1\leqslant i$. Then $cf(G)=n+\sum _{i\geqslant 1} k_i \lceil \frac{i}{2}\rceil$.

Proof

We first prove $cf(G)\geqslant n+\sum _{i\geqslant 1} k_i \lceil \frac{i}{2}\rceil$. Then we construct a complete forcing set of size $n+\sum _{i\geqslant 1} k_i \lceil \frac{i}{2}\rceil$.

Let $S$ be a complete forcing set of $G$ with $|S|=cf(G)$. By Theorem 2.1 and Lemma 3.1, $S$ must contain one edge $e$ from each type-set $C(r)$ of each linear hexagon $r$. If $e$ is not shared, then we exchange $e$ and the shared edge of $C(r)$. Hence we obtain a new edge subset $S'$ such that $|S|\geqslant |S'|$ and $S'$ contains two shared edges of every linear hexagon. Note that $S'$ is not necessarily a complete forcing set. In what follows we give the lower bound on $cf(G)$ by counting $|S'|$.

By the construction of $S'$, every linear hexagon contributes at least $\frac{1}{2}+\frac{1}{2}=1$ to $|S'|$. Therefore, all linear hexagons in $G$ have total contributions at least $(n-n^*)$ to $|S'|$, where $n^*$ is the number of kinks in $G$. Let $K$ be any kink segment with $i$ hexagons. We denote all hexagons in $K$ by $h_1, h_2, \ldots , h_i$ in turn. Each $h_j$ $(1\leqslant j\leqslant i)$ has exactly one type-set, say $M(h_j)$, in which no edges are shared, so $M(h_j)$ contributes at least $1$ to $|S|$ (therefore to $|S'|$ too, since $S$ and $S'$ have the same construction on kink segments except ended shared edges) by Theorem 2.1; while the other type-set of $h_j$ contributes at least $\frac{1}{2}$ to $|S|$ (further to $|S'|$). Hence the hexagon $h_j$ contributes at least $\frac{3}{2}$ to $|S'|$. If $i$ is odd (in this case $i\ne n$), by the choice of $S'$, then the shared edges of $h_1$ and $h_i$ with linear hexagons are contained in $S'$. Hence, there exists some hexagon, say $h$, in $K$ with at least two shared edges in $S'$, which belong to the common type-set of $h$, and so $h$ contributes at least $2$ to $|S'|$. Then all hexagons in $K$ contribute at least $(i+\lceil \frac{i}{2} \rceil )$ in total to $|S'|$. Therefore

In what follows we construct a complete forcing set of size $n+\sum _{i\geqslant 1} k_i \lceil \frac{i}{2}\rceil$. First we construct a set $S$ of cardinality $n+\sum _{i\geqslant 1} k_i \lceil \frac{i}{2}\rceil$. Then we prove that $S$ is a complete forcing set of $G$ by Theorem 2.1.

First, we construct edges in the type-set of each hexagon containing a shared edge (Note that two type-sets of a linear hexagon are such ones). If $G$ itself is a kink segment, i.e., all hexagons in it are kinks, then we alternately choose shared edges of $G$ into $S$. Otherwise, we first choose both shared edges of each linear hexagon into $S$. Then for every kink segment $K$ with $i$ kinks ($1\leqslant i< n$), say $h_1, h_2, \ldots , h_i$ in clockwise order, we select the shared edge of $h_{2j}$ and $h_{2j+1}$ into $S$ for $1\leqslant j\leqslant \lceil \frac{i}{2} \rceil -1$. Secondly, we collectively construct edges in the type-set of all kinks containing no shared edges into $S$ in clockwise order such that, beginning from any start position $P$ in $G$ except in Subsubcase 2.2.1 (see below), we choose two respective internal edges, say $e_1$ and $e_2$, of two successive kinks into $S$, then two respective external edges, say $e_3$ and $e_4$, of two subsequent successive kinks into $S$, we proceed the process until no kinks will be assigned (see Fig. 3 for an example). Hence we obtain an edge subset $\{e_1, e_2, \ldots , e_{h^*}\}\subseteq S$. Note that $e_{h^*-1}, e_{h^*}, e_1, e_2$ are maybe the unique four successive internal edges in $S$ and any edge in $S$ has a 3-degree vertex as an endpoint.

Fig. 3

Illustration for the construction of edges in $S$ in the proof of Theorem 3.9. Bold solid edges represent non-shared edges in $S$, while bold dotted edges represent shared edges in $S$; hexagons with letter ‘$K$’ at their centers are kinks; the dotted straight line represents the start position $P$ mentioned in the proof

Secondly, we count edges in $S$, i.e., compute $|S|$. If $G$ itself is a kink segment, then $|S|=\frac{n}{2}+n=\frac{3n}{2}=n+\sum _{i\geqslant 1}k_i\lceil \frac{i}{2}\rceil$, because in this case, $k_i$ equals $1$ if $i=n$, and equals $0$ otherwise. Otherwise, since the total number of shared edges in $G$ is $n$ and the number of shared edges of $G$ not in $S$ is equal to $\sum _{i\geqslant 1}k_i(i-1-(\lceil \frac{i}{2} \rceil -1))=\sum _{i\geqslant 1}k_i(i-\lceil \frac{i}{2} \rceil )$, the number of shared edges in $S$ is equal to $n-\sum _{i\geqslant 1}k_i(i-\lceil \frac{i}{2}\rceil )$. From the construction of $S$, the number of non-shared edges is obviously equal to the number of kinks, i.e., $\sum _{i\geqslant 1}i k_i$. So $|S|=n-\sum _{i\geqslant 1}k_i(i-\lceil \frac{i}{2}\rceil )+\sum _{i\geqslant 1}i k_i=n+\sum _{i\geqslant 1}k_i\lceil \frac{i}{2} \rceil .$

Finally, we prove $S$ is a complete forcing set of $G$. By Theorem 2.1, it is sufficient to prove that the intersection of $S$ and any type-set of any nice cycle is non-empty. By the construction of $S$, we know the intersection of $S$ and any type-set of any (nice) hexagon in $G$ is non-empty. Further, the intersection of $S$ and any type-set of any nice cycle containing no non-hexagonal internal face is non-empty by Theorem 3.8. So in what follows it is sufficient to prove that the intersection of $S$ and any type-set of any nice cycle, say $C$, containing the non-hexagonal internal face of $G$ is non-empty, i.e., $S$ contains at least one edge in each type-set of $C$.

If $C=C_0(G)$, then by Corollary 3.7 (2) two internal edges $e_1$ and $e_2$ in $S$ belong to two type-sets of $C$, respectively. Similarly, if $C=C_1(G)$, then two external edges $e_3$ and $e_4$ in $S$ belong to two type-sets of $C$, respectively. In what follows we assume that $C$ is neither $C_0(G)$ nor $C_1(G)$.

Case 1 $C$ contains a shared edge in $S$.

Let $e$ be a shared edge in $S$ of $C$, $K_1$ and $K_2$ two kinks closely next to $e$. By Theorem 3.6, one of them, say $K_1$, is in $C$ and the other $K_2$ is out of $C$ (see Fig. 4).

Subcase 1.1 Either an external edge $e_1'$ of $K_1$ or an internal edge $e_2'$ of $K_2$ is in $S$.

The edge $e$ and any of $e_1'$ and $e_2'$ belong to two type-sets of $C$ by Corollary 3.4.

Subcase 1.2 Both an internal edge $e_1^*$ of $K_1$ and an external edge $e_2^*$ of $K_2$ are in $S$ (see Fig. 4).

Let $K_3$ be the kink next to $K_2$ other than $K_1$. Then an external edge $e_3^*$ of $K_3$ is in $S$ by the construction of $S$. If $K_3$ is in $C$, then $e_3^*$ is in $C$. So $e_3^*, e$ belong to two type-sets of $C$ respectively by Corollaries 3.7 (1) and 3.4. Otherwise, if we denote by $K_4$ the kink next to $K_3$ other than $K_2$, then $K_4$ is also out of $C$ by Theorem 3.6 and an internal edge $e_4^*$ of $K_4$ is in $S$ by the construction of $S$ (see Fig. 4). Hence $e$ and $e_4^*$ belong to two type-sets of $C$ respectively by Corollary 3.4.

Fig. 4

Illustration for Subcase 1.2 in Theorem 3.9. The dotted curve represents a part of $C$; bold dotted or solid edges represent edges in $S$

Case 2 $C$ does not contain shared edges in $S$.

In this case shared edges on $C$ are contained in kinks. Note that each hexagonal chain in $G$ divided by shared edges of $C$ contains at least 3 kinks in $G$. If there exists such a hexagonal chain containing exactly one kink, then $C$ contains a shared edge in $S$ by the construction of $S$, which contradicts the assumption.

Subcase 2.1 There exists a hexagonal chain in $G$ divided by shared edges of $C$ out of $C$ containing at least five successive kinks.

In this case, $S$ contains internal edges of at least two successive kinks among the five kinks, then these two internal edges belong to two type-sets of $C$ respectively by the construction of $S$ and Corollary 3.7 (2).

Subcase 2.2 Every hexagon chain in $G$ divided by shared edges of $C$ out of $C$ contains exactly three kinks.

Subsubcase 2.2.1 $G$ is convex.

In this case, there are at least two kink segments in $G$ and exactly two hexagonal chains, say $A, B$, in $G$ divided by shared edges of $C$, each of which contains three kinks. We denote by $K_1, K_2, \ldots , K_6$ all kinks in clockwise order and assume the first three ones belong to $A$ (see Fig. 5). By the construction of $S$ about shared edges, we know $K_6$ and $K_1$ are adjacent, $K_3$ and $K_4$ are adjacent. Hence by Eq. (1), $G$ has either two kink segments of length $3$ (see Fig. 5a) or four kink segments of length 1, 2, 1, 2 (see Fig. 5b), respectively. In each case there are exactly two shared edges not in $S$. Hence a nice cycle containing the non-hexagonal internal face in $G$ other than $C_0(G)$ and $C_1(G)$ is either $C$ or $C'=C\oplus (C_0(G)\cup C_1(G))$. We assign internal edges of $K_2, K_3, K_4, K_5$, external edges of $K_6, K_1$ into $S$ by choosing an appropriate start position $P$ as Fig. 5. Then internal edges of $K_2, K_3$ (resp. $K_4, K_5$) belong to two type-sets of $C$ (resp. $C'$) respectively by Corollary 3.7 (2).

Fig. 5

Illustration for Subsubcase 2.2.1 in Theorem 3.9. $C$ is indicated by the dotted cycle. Bold edges represent non-shared edges in $S$

Subsubcase 2.2.2 $G$ is not convex.

We take any hexagonal chain, say $A$, in $G$ divided by shared edges of $C$ out of $C$ with three kinks, say $K_4, K_5, K_6$ in clockwise order, let $K_1, K_2, K_3$ be the three successive kinks to the left of $A$, $K_7, K_8, K_9$ be the three successive kinks to the right of $A$ (see Fig. 6).

If there are two internal edges of two successive kinks among $K_4, K_5$ and $K_6$ in $S$, then these two internal edges belong to two type-sets of $C$ by Corollary 3.7 (2). Otherwise, without loss of generation we assume the intersections of $C$ and $K_5, K_6$ are external edges (see Fig. 6). Then the intersection, say $e$, of $C$ and $K_4$ is an internal edge. If $e$ does not belong to the unique four successive internal edges in $S$, then the intersections of $S$ and $K_1, K_2$ are external, which belong to two type-sets of $C$ by Corollary 3.7 (2). Then we assume $e$ belongs to the unique four successive internal edges in $S$. If the length of the hexagonal chain, say $B$, in $G$ divided by shared edges of $C$ to the right of $A$ does not less than four, then $B$ contains two successive external edges in $S$, which belong to two type-sets of $C$ by Corollary 3.7 (2). So we assume $B$ contains exactly three successive kinks $K_4$, $K_5$ and $K_6$. Note that in this case there are at least four hexagonal chains in $G$ divided by shared edges of $C$ because there are at least eight kinks and each hexagonal chain has an odd number ($\geqslant$3) of kinks. Let $K_{10}, K_{11}, K_{12}$ be three successive kinks in the hexagonal chain next to $B$ other than $A$, which does not contain $K_1$. Since the intersections of $S$ and $K_7, K_8$ are internal edges and the intersection of $S$ and $K_9$ is an external edge, the intersections of $S$ and $K_{11}, K_{12}$ are two successive internal edges, which belong to two type-sets of $C$ by Corollary 3.7 (2). $\square$

Fig. 6

Illustration for Subsubcase 2.2.2 in Theorem 3.9. Bold edges represent non-shared edges in $S$; the dotted cycle represents the nice cycle $C$

Example Let $G$ be a primitive coronoid as in Fig. 7. In $G$, there are 18 hexagons, 4 kink segments of length 1, 2, 5, 6, respectively. So $k_i=1$ for $i=1, 2, 5, 6$, $k_i=0$ for other integers $i$. By Theorem 3.9,

$$\begin{aligned} cf(G)= & {} 18+1\times \Big \lceil \frac{1}{2}\Big \rceil +1\times \Big \lceil \frac{2}{2}\Big \rceil +1\times \Big \lceil \frac{5}{2}\Big \rceil +1\times \Big \lceil \frac{6}{2}\Big \rceil \\= & {} 18+1+1+3+3\\= & {} 26. \end{aligned}$$

Fig. 7

A primitive coronoid $G$ with its kinks indicated by placing letters ‘K’ at centers of them. Bold edges represent edges in a minimum complete forcing set

4 Conclusion

In this paper we discuss complete forcing numbers of primitive coronoids and give an explicit analytical expression for the complete forcing number of a primitive coronoid in terms of the number of hexagons and lengths of kink segments in it, similar to expressions for complete forcing numbers of hexagonal chains shown in Xu et al. (2015c). But the proof is more complicated, partially because of non-trivial nice cycles containing the non-hexagonal internal face.

For a catacondensed hexagonal system $G$, the necessary and sufficient condition for set $S$ to be a complete forcing set of $G$ is given in Xu et al. (2015c).

Theorem 4.1

Xu et al. (2015c) Let $G$ be a catacondensed hexagonal system with edge set $E(G)$. A subset $S$ of edge set $E(G)$ is a complete forcing set if and only if $S$ has a non-empty intersection with each type-set of any hexagon.

Whether is the above theorem true for primitive coronoids? Unfortunately, it is not true, a counterexample is shown in Fig. 8.

Fig. 8

A counterexample for primitive coronoids relating to Theorem 4.1. Bold edges represent a subset $S$ of the edge set which has non-empty intersection with either of type-sets of any hexagon. The dotted cycle represents a nice cycle of which there exists a type-set not intersecting with $S$, i.e., consisting of edges from black vertex to white vertex in clockwise order