ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.09
https://doi.org/10.26493/1855-3974.2706.3c8
(Also available at http://amc-journal.eu)
Complete forcing numbers of graphs*
Xin He , Heping Zhang †
School of Mathematics and Statistics, Lanzhou University, Lanzhou,
Gansu 730000, P.R. China
Received 10 October 2021, accepted 30 June 2022, published online 13 December 2022
Abstract
The complete forcing number of a graph G with a perfect matching is the minimum
cardinality of an edge set of G on which the restriction of each perfect matching M is a
forcing set of M . This concept can be view as a strengthening of the concept of global
forcing number of G. Došlić in 2007 obtained that the global forcing number of a con-
nected graph is at most its cyclomatic number. Motivated from this result, we obtain that
the complete forcing number of a graph is no more than 2 times its cyclomatic number
and characterize the matching covered graphs whose complete forcing numbers attain this
upper bound and minus one, respectively. Besides, we present a method of constructing a
complete forcing set of a graph. By using such method, we give closed formulas for the
complete forcing numbers of wheels and cylinders.
Keywords: Perfect matching, global forcing number, complete forcing number, cyclomatic number,
wheel, cylinder.
Math. Subj. Class. (2020): 05C70, 05C90, 92E10
1 Introduction
Let G be a graph with vertex set V (G) and edge set E(G). A matching of G is a set of
disjoint edges of G. A perfect matching M of G is a matching that covers all vertices of
G. An edge of G is termed allowed if it lies in some perfect matching of G and forbidden
otherwise. A forcing set of M is a subset of M contained in no other perfect matching of
G. The forcing number of M is the minimum possible cardinality of forcing sets of M . We
may refer to a survey [6] on this topic. A subset S ⊆ E(G) \M is called an anti-forcing
set of M [14] if G − S has a unique perfect matching M . The anti-forcing number of M
is the smallest cardinality of anti-forcing sets of M .
*The authors are grateful to anonymous reviewers for their careful reading and valuable suggestions to improve
this manuscript. This work is supported by National Natural Science Foundation of China (Grant No. 11871256
and 12271229).
†Corresponding author.
E-mail addresses: hex2015@lzu.edu.cn (Xin He), zhanghp@lzu.edu.cn (Heping Zhang)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P2.09
Let G be a graph with a perfect matching. Concerning all perfect matchings of G,
Vukičević et al. [21, 22] introduced the concept of global (or total) forcing set, which is
defined as a subset of E(G) on which there are no two distinct perfect matchings coincid-
ing. The minimum possible cardinality of global forcing sets is called the global forcing
number of G. For more about the global forcing number of a graph, the reader is referred
to [3, 7, 20, 27].
As a strengthening of the concept of global forcing set of G, Xu et al. [24] proposed the
concept of the complete forcing set of G, which is defined as a subset of E(G) on 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, denoted by cf(G). If G has at least two perfect
matchings, then cf(G) is larger than the global forcing number of G [24].
A subgraph G0 of G is said to be nice if G−V (G0) has a perfect matching. Obviously,
an even cycle C of G is nice if and only if there is a perfect matching M of G such that
E(C) ∩M is a perfect matching of C. We call each of the two perfect matchings of C a
frame (or a typeset [24]) of C, which was ever used in [1] to obtain a min-max theorem for
the Clar problem on 2-connected plane bipartite graphs.
Xu et al. established the following equivalent condition for a subset of edges of a graph
to be a complete forcing set.
Theorem 1.1 ([24]). Let G be a graph with a perfect matching. Then S ⊆ E(G) is a
complete forcing set of G if and only if for any nice cycle C of G, the intersection of S and
each frame of C is nonempty.
Let S be a complete forcing set of G. For a perfect matching M of G, from Theo-
rem 1.1, S\M contains at least one edge of every M -alternating cycle of G. By Lemma 2.1
of [14], S \M is an anti-forcing set of M . So a complete forcing set of G both forces and
antiforces each perfect matching. Further, Chan et al. [4] obtained that the complete forc-
ing number of a catacondensed hexagonal system is equal to the number of hexagons plus
the Clar number and presented a linear-time algorithm for computing it. Besides, some
certain explicit formulas for the complete forcing numbers of rectangular polynominoes,
polyphenyl systems, spiro hexagonal systems and primitive coronoids have been derived
[5, 15, 16, 23]. In recent papers [11, 12], we established a sufficient condition for an edge
set of a hexagonal system (HS) to be a complete forcing set in terms of elementary edge-cut
cover, which yields a tight upper bound on the complete forcing numbers of HSs. For a
normal HS, we gave two lower bounds on its complete forcing number by the number of
hexagons and matching numbers of some subgraphs of its inner dual graph, respectively.
In addition, we showed that the complete forcing numbers of catacondensed HSs, normal
HSs without 2× 3 subsystems, parallelogram, regular hexagon- and rectangle-shaped HSs
attain one of the two above lower bounds.
Let c(G) = |E(G)|− |V (G)|+ω(G) denote the cyclomatic number of G, where ω(G)
is the number of components of G. In 2007, Došlić [7] obtained that the global forcing
number of a connected graph is at most its cyclomatic number and gave a characterization:
a connected (bipartite) graph has the global forcing number attaining its cyclomatic number
if and only if each cycle is nice (such graphs are called 1-cycle resonant graphs; see [9]).
As a corollary, the global forcing number of any catacondensed HS is equal to the number
of hexagons.
Motivated by Došlić’s result, in this paper we obtain that the complete forcing number
X. He and H. Zhang: Complete forcing numbers of graphs 3
of a graph is no more than 2 times its cyclomatic number by presenting a method of con-
structing a complete forcing set of a graph (see the next section). Moreover, in Section 3,
we show that the complete forcing number of a matching covered graph attains the above
upper bound if and only if such graph is either K2 (a complete graph with 2 vertices) or an
even cycle. Besides, we characterize the matching covered graphs whose complete forcing
numbers are equal to 2 times their cyclomatic numbers minus 1 in terms of ear decompo-
sition. In the last section, we present some lower bounds on the complete forcing numbers
of some types of graphs including plane elementary bipartite graphs and cylinders. Com-
bining such methods, we give closed formulas for the complete forcing numbers of wheels
and cylinders.
2 An upper bound on complete forcing number
All graphs considered in this paper are simple and all the bipartite graphs are given a proper
black and white coloring: any two adjacent vertices receive different colors.
Let G be a graph. Suppose that V ′ is a nonempty subset of V (G). The subgraph of
G whose vertex set is V ′ and whose edge set is the set of those edges of G that have both
end-vertices in V ′ is called the subgraph of G induced by V ′ and is denoted by G[V ′]. The
induced subgraph G[V \V ′] is denoted by G−V ′. For E′ ⊆ E(G), the spanning subgraph
(V (G), E(G) \ E′) is denoted by G− E′ [2]. For a nonempty proper subset V ′ of V (G),
the set of all edges of G having exactly one end-vertex in V ′ is called an edge cut of G and
denoted by ∂G(V ′) (or simply ∂(V ′)).
For v ∈ V (G) and e ∈ E(G), for simplicity we use G− v, G− e and ∂(v) to represent
G − {v}, G − {e} and ∂({v}) respectively. Further the cardinality of ∂G(v) is called the
degree of v in G and is denoted by dG(v) (or simply d(v)).
In this section, we will present a method of constructing a complete forcing set of G
in terms of elementary edge cut, which was introduced in [19, 26] to show the existence
of perfect matchings in HS and plays an important role in resonance theory of graphs
[13, 25, 28] especially in the computation of Clar number of HSs [10]. Elementary edge
cut was previously defined in bipartite graphs, we extend this concept to general graphs as
follows.
We call an edge cut D of G an elementary edge cut (e-cut for short) if it satisfies the
following three conditions:
(1) ω(G − D) = ω(G) + 1, that is, there are exactly two components O1 and O2 of
G−D that are different from of all components of G.
(2) At least one of O1 and O2 is a bipartite graph.
(3) All edges of D are incident with the vertices of the same color in one bipartite com-
ponent of O1 and O2 (for example, the bold edges of G1 in Figure 10 form an e-cut
of G1).
A bridge of G is an edge cut of G consisting of exactly one edge. A cut-vertex of G is
a vertex whose deletion increases the number of components. A block of G is a maximal
connected subgraph of G that has no cut-vertices. Each block with at least 3 vertices is
2-connected. The blocks of a loopless graph are its isolated vertices, bridges, and maximal
2-connected subgraph. A block of G that contains exactly one cut-vertex of G is called an
end-block of G.
4 Ars Math. Contemp. 23 (2023) #P2.09
Let D be an e-cut of a graph G with at least two edges. Then we define an e-cut deletion
operation (simply ED operation) of G in the following steps:
(1) Delete D from G,
(2) Delete the set B consisting of all bridges of G−D, and
(3) Delete the isolated vertices of G−D −B.
Let G′ be the subgraph obtained from G by an ED operation. Then G′ has neither
isolated vertices nor bridges. If G′ is not empty, then each block of G′ is 2-connected. Let
v′ be a non-cut-vertex of a block of G′ with at most one cut-vertex of G′. Then ω(G′ −
∂G′(v
′)) = ω(G′) + 1 and v′ is a component of G′ − ∂G′(v′), so ∂G′(v′) is an e-cut of G′
with at least 2 edges and we can do an ED operation on G′. If we can do l ED operations
from G and obtain the following subgraph sequence G = G1 ⊃ G2 ⊃ · · · ⊃ Gl+1,
where Gi is not empty graph and Gi+1 is obtained by doing an ED operation from Gi for
i = 1, 2, . . . , l, then we call this procedure an e-cut decomposition from G1 to Gl+1. Let
Di be the deleted e-cut from Gi. Then
c(Gi −Di) = |E(Gi)| − |Di| − |V (Gi)|+ ω(Gi) + 1 = c(Gi)− (|Di| − 1).
Let Bi be the set of bridges deleted from Gi −Di. Then we have
c((Gi −Di)−Bi) = c(Gi −Di) = c(Gi)− (|Di| − 1).
Since deleting the isolated vertices from Gi − Di − Bi keeps its cyclomatic number un-
changed,
c(Gi+1) = c((Gi −Di)−Bi) = c(Gi)− (|Di| − 1).
So, we have
c(Gi)− c(Gi+1) = |Di| − 1. (2.1)
Since |Di| ≥ 2, Equation (2.1) implies that an ED operation on Gi decrease the cyclomatic
number by at least 1.
From the above discussion, we have the following result.
Lemma 2.1. If a graph G has an e-cut with at least two edges, then there exists an e-cut
decomposition from G to empty graph.
Lemma 2.2. Let G be a graph without isolated vertices or bridges. If H is a 2-connected
induced subgraph of G, then there exists an e-cut decomposition from G to H .
Proof. If G is not 2-connected, then there is a block B of G such that H is not an induced
subgraph of B and B contains at most one cut-vertex of G. Since G has neither isolated
vertices nor bridges, B is 2-connected. Let v1 be a vertex of B that is not a cut-vertex of
G. Then ∂G(v1) is an e-cut of G with at least two edges. We can use ∂G(v1) to do an ED
operation on G. If G is 2-connected and G ̸= H , let v2 be a vertex of V (G) \ V (H). Then
∂G(v2) is an e-cut of G with at least two edges. We can use ∂G(v2) to do an ED operation
on G. In either of the above two cases, we can see that H is still an induced subgraph of
the resulting graph. Clearly, we can do ED operations repeatedly like the above until the
resulting subgraph is H .
X. He and H. Zhang: Complete forcing numbers of graphs 5
Lemma 2.3. Let G be a graph that admits a perfect matching and F be the set of all
forbidden edges of G. If there exists an e-cut decomposition from G − F = G1 to Gl+1
(l ≥ 1) such that Gl+1 is empty graph or each cycle of Gl+1 is not a nice cycle of G, then
D1 ∪D2 ∪ · · · ∪Dl is a complete forcing set of G, where Di (i = 1, 2, . . . , l) is the e-cut
deleted from Gi in the e-cut decomposition. Further, cf(G) ≤ c(G) + l − c(Gl+1).
Proof. For i = 1, 2, . . . , l, let Bi be the set of bridges deleted from Gi − Di in the e-cut
decomposition. Then E(G) can be partitioned into F ∪D1 ∪B1 ∪D2 ∪B2 ∪ · · · ∪Dl ∪
Bl ∪ E(Gl+1). Since every edge of a nice cycle C is allowed, E(C) ∩ F = ∅.
Claim. For i = 1, 2, . . . , l, if there is a nice cycle C of G that has an edge in Di ∪Bi, then
each frame of C intersects D1 ∪D2 ∪ · · · ∪Di.
Proof. We shall proceed by induction on i. For i = 1, if E(C)∩B1 ̸= ∅, then E(C)∩D1 ̸=
∅. Choose an edge e1 in E(C) ∩ D1. Since D1 is an e-cut of G1, there is a bipartite
component O1 of G1 − D1 such that all edges of D1 are incident with the same colored
vertices of O1 (say black). After C passes through e1 to black end-vertex in O1, C must
pass through another edge of D1 from black end-vertex in O1. Let e2 be the first such edge.
Then the path of C1 between black vertices of e1 and e2 in O1 has even length. This yields
that edges e1 and e2 in D1 belong to different frames of C and the claim holds for i = 1.
Suppose that the claim holds for i ≤ l − 1. We shall prove it for i + 1. If C has an edge
in E(G) \E(Gi+1), that is, C has some edge in D1 ∪B1 ∪D2 ∪B2 ∪ · · · ∪Di ∪Bi, by
the induction hypothesis, the intersection of each frame of C and D1 ∪ D2 ∪ · · · ∪ Di is
nonempty. So we may assume that E(C) ⊆ E(Gi+1). Since C has an edge in Di+1∪Bi+1,
similarly we have that each frame of C must have an edge in Di+1. Consequently, the claim
holds.
Since Gl+1 is empty graph or every cycle of Gl+1 is not a nice cycle of G, every nice
cycle of G contains an edge in D1∪B1∪D2∪B2∪· · ·∪Dl∪Bl. By the claim, each frame
of each nice cycle of G intersects D1∪D2∪· · ·∪Dl. So, by Theorem 1.1, D1∪D2∪· · ·∪Dl
is a complete forcing set of G.
From Equation (2.1), we have
c(G1)− c(Gl+1) =
l∑
i=1
(|Di| − 1), (2.2)
and then
l∑
i=1
|Di| = c(G1) + l − c(Gl+1).
Since G1 = G− F , c(G1) ≤ c(G) and
cf(G) ≤ |D1 ∪D2 ∪ · · · ∪Dl| = c(G1) + l − c(Gl+1) ≤ c(G) + l − c(Gl+1).
From Lemma 2.3, we have the following upper bound on the complete forcing number.
Theorem 2.4. Let G be a graph that admits a perfect matching. Then cf(G) ≤ 2c(G).
Proof. If G has a unique perfect matching, then cf(G) = 0, and the conclusion holds. If
G has at least two perfect matchings, let F be the set of all forbidden edges of G. Then
6 Ars Math. Contemp. 23 (2023) #P2.09
each K2 block of G − F is a component, so there is a 2-connected block B of G − F
with at most one cut-vertex of G − F . Let v be a vertex of B that is not a cut-vertex of
G− F . Then ∂G−F (v) is an e-cut of G− F with at least two edges. By Lemma 2.1 there
exists an e-cut decomposition from G − F to empty graph: G1 ⊃ G2 ⊃ · · · ⊃ Gl+1,
where G1 = G − F and Gl+1 = ∅. For i = 1, 2, . . . , l, let Di be the e-cut deleted from
Gi in this e-cut decomposition. From Equation (2.2), since |Di| ≥ 2 and c(G1) ≤ c(G),
we have l ≤
∑l
i=1(|Di| − 1) = c(G1) ≤ c(G). Combining with Lemma 2.3, we have
cf(G) ≤ c(G) + l − c(Gl+1) ≤ 2c(G).
3 Some extremal matching covered graphs
A connected graph G is said to be matching covered if it has at least two vertices and
each edge is allowed. Every matching covered graph with at least four vertices is 2-
connected [18].
In this section, we will characterize the matching covered graphs whose complete forc-
ing numbers attain the upper bound given in Theorem 2.4 and minus one, respectively.
Theorem 3.1. Let G be a matching covered graph. Then cf(G) = 2c(G) if and only if G
is either K2 or an even cycle.
Proof. The sufficiency is obvious. So we consider the necessity. If c(G) = 0, then G is
a tree. Since G is matching covered, G can only be K2. For c(G) ≥ 1, suppose to the
contrary that G is not an even cycle. Then G has a vertex v with degree at least 3. Let
D1 = ∂(v). Then since G is 2-connected, G − D1 has exactly two components and D1
is an e-cut with |D1| ≥ 3. We use D1 to do an ED operation on G1 = G and obtain
G2, and then we do ED operations from G2 repeatedly until the empty graph is obtained.
Consequently, we obtain an e-cut decomposition G = G1 ⊃ G2 ⊃ · · · ⊃ Gl+1 = ∅
(l ≥ 1). For i = 2, 3, . . . , l, let Di be the e-cut deleted from Gi in this e-cut decomposition.
By Equation (2.1), c(G2)−c(G1) = |D1|−1 ≥ 2 and c(Gi+1)−c(Gi) = |Di|−1 ≥ 1 (i =
2, 3, . . . , l). Combining with Equation (2.2), we have l + 1 ≤
∑l
i=1(|Di| − 1) = c(G)−
c(Gl+1), and thus l ≤ c(G)− 1. By Lemma 2.3, c(G) ≤ 2c(G)− 1, a contradiction.
Corollary 3.2. Let G be a graph with a perfect matching. Then cf(G) = 2c(G) if and
only if
(i) each forbidden edge of G is a bridge, and
(ii) each component of the graph obtained by deleting all forbidden edges from G is
either K2 or an even cycle.
Proof. Let G0 be the graph obtained from G by deleting all forbidden edges. Since each
forbidden edge of G does not appear in any minimum complete forcing set of G, cf(G) =
cf(G0). Let O1, O2, . . . , Ot (t ≥ 1) be the components of G0. By Theorem 2.4 we have
cf(G) = cf(G0) =
t∑
i=1
cf(Oi) ≤ 2
t∑
i=1
c(Oi) = 2c(G0) ≤ 2c(G).
In the above expression, Theorem 3.1 implies that the third equality holds if and only if
each Oi is either K2 or an even cycle, and the fifth equality holds if and only if G0 and G
have the same cyclomatic number, that is, each forbidden edge of G is a bridge.
X. He and H. Zhang: Complete forcing numbers of graphs 7
A connected graph G is said to be elementary if all its allowed edges form a connected
subgraph of G. A connected bipartite graph is elementary if and only if each edge is al-
lowed [17]. An elementary bipartite graph has the so-called “bipartite ear decomposition”.
Let x be an edge. Join the end vertices of x by a path P1 of odd length (the so-called
“first ear”). We proceed inductively to build a sequence of bipartite graphs as follows: If
Gr−1 = x + P1 + P2 + · · · + Pr−1 has already been constructed, add the r-th ear Pr (a
path of odd length) by joining any two vertices in different colors of Gr−1 such that Pr has
no other vertices in common with Gr−1. The decomposition Gr = x+P1+P2+ · · ·+Pr
will be called an (bipartite) ear decomposition of Gr. It is known that a bipartite graph G
is elementary if and only if G has a bipartite ear decomposition [17]. We can see that the
number r of ears is equal to the cyclomatic number of G.
2P
r
b
2b
3b
3w
r
w
2w
( )a ( )b
3P
r
P
1x P+
'
1P
'
2P
'
3P
a
b
Figure 1: Two examples for graphs G with cf(G) = 2c(G)− 1.
Theorem 3.3. Let G be a matching covered graph. Then cf(G) = 2c(G) − 1 if and only
if G is a bipartite graph and one of the following holds :
(i) c(G) = 2 (see Figure 1(a));
(ii) G has an ear decomposition G = x + P1 + P2 + · · · + Pr (r ≥ 3) such that one
frame of x+P1 contains at least r−1 edges w2b2, w3b3, . . . , wrbr and the two ends
of P2, P3, . . . , Pr are the two end-vertices of w2b2, w3b3, . . . , wrbr, respectively (see
Figure 1(b)).
Proof. Sufficiency. (i) If c(G) = 2, by the ear decomposition of G, G contains two 3-
degree vertices, denoted by a and b. Let P ′1, P
′
2, P
′
3 be the 3 internally disjoint paths from
a to b (see Figure 1(a)) and S be a complete forcing set of G. If |S| ≤ 2, then one of
P ′1, P
′
2 and P
′
3 has no edges in S, say P
′
1. We can see that one of the two nice cycles
P ′1 ∪ P ′2 and P ′1 ∪ P ′3 has a frame containing no edges of S, which contradicts that S is a
complete forcing set by Theorem 1.1. So cf(G) ≥ 3. Conversely, we can see that ∂G(a)
is a complete forcing set of G, which means that cf(G) ≤ 3. Consequently, we have
cf(G) = 3 = 2c(G)− 1.
8 Ars Math. Contemp. 23 (2023) #P2.09
(ii) For 2 ≤ i ≤ r, let Ci = Pi∪{wibi}. Then we can see that C2, C3, . . . , Cr are r−1
vertex-disjoint nice cycles of G. Let S be a complete forcing set of G. By Theorem 1.1,
each frame of Ci (2 ≤ i ≤ r) has at least one edge of S, so each Ci contains 2 edges of S.
Further the frame of the nice cycle x+P1 that does not contain {w2b2, w3b3, . . . , wrbr} has
an edge in S. So |S| ≥ 2r − 1. Conversely, let D1 = ∂G(b2) and Di (i = 2, 3, . . . , r − 1)
be any two adjacent edges of Ci+1. We use D1, D2, . . . , Dr−1 to do ED operations from
G in turn and obtain empty graph finally. By Lemma 2.3, D1 ∪ D2 ∪ · · · ∪ Dr−1 is a
complete forcing set of G and cf(G) ≤ |D1 ∪D2 ∪ · · · ∪Dr−1| = 3+2(r− 2) = 2r− 1.
Consequently, we have cf(G) = 2r − 1 = 2c(G)− 1.
Necessity. If c(G) = 0 or 1, then G is K2 or an even cycle. By Theorem 3.1, cf(G) =
2c(G), contradicting cf(G) = 2c(G) − 1. So c(G) ≥ 2 and |V (G)| ≥ 4. Since G is
matching covered, G is 2-connected.
Claim 1. For an e-cut decomposition from G = G1 to Gl+1 = ∅, if there is an integer k
(1 ≤ k ≤ l) such that |Dk| ≥ 4 or there are two integers m and n (1 ≤ m < n ≤ l) such
that |Dm| ≥ 3 and |Dn| ≥ 3, then cf(G) ≤ 2c(G)− 2.
Proof. If |Dk| ≥ 4 (1 ≤ k ≤ l), then since |Di| ≥ 2 for i = 1, 2, . . . , k − 1, k + 1, . . . , l,∑l
i=1(|Di| − 1) ≥ l + 2. From Equation (2.2), we have l ≤ c(G)− 2, and thus cf(G) ≤
2c(G)− 2 by Lemma 2.3.
If |Dm| ≥ 3 and |Dn| ≥ 3 (1 ≤ m < n ≤ l). Then since |Di| ≥ 2 (i = 1, 2, . . . ,
m− 1,m+1, . . . , n− 1, n+1, . . . , l),
∑l
i=1(|Di| − 1) ≥ l+2. From Equation (2.2), we
have l ≤ c(G)− 2, and thus cf(G) ≤ 2c(G)− 2 by Lemma 2.3.
If G has a vertex v0 with degree at least 4, let D1 = ∂(v0). Since G is 2-connected,
G − ∂(v0) has exactly two components and D1 is an e-cut of G. Then we can give an
e-cut decomposition from G to empty graph by taking D1 as the first e-cut. By Claim 1,
cf(G) ≤ 2c(G) − 2, a contradiction. Thus dG(v) ≤ 3 for each vertex v ∈ V (G). In
addition, since c(G) ≥ 2, G has a 3-degree vertex v1. Since G is 2-connected, G − v1 is
connected.
Claim 2. G is a bipartite graph.
Proof. Suppose to the contrary that G is not a bipartite graph. Let v be a vertex of G.
Then G − v is not a bipartite graph as well. Otherwise, G − v has a bipartition (W,B)
(|W | < |B|). If v is adjacent to a vertex w of W in G, then vw is a forbidden edge of G,
which contradicts that G is matching covered. So v can only be adjacent to vertices of B
in G, and thus G is a bipartite graph, a contradiction to the supposition. Hence, G− v1 has
an odd cycle C1.
Let D1 = ∂(v1). Since G is 2-connected, G−D1 has exactly two components and D1
is an e-cut of G with |D1| = 3. We obtain G2 by doing an ED operation on G1 = G via D1.
Since G[V (C1)] is 2-connected and G[V (C1)] is still a subgraph of G2, from Lemma 2.2,
there exists an e-cut decomposition from G2 to G[V (C1)] = Gm. For i = 2, 3, . . . ,
m − 1, we denote by Di the deleted e-cut from Gi in this e-cut decomposition. If Gm
has a 3-degree vertex vm, let Dm = ∂G[V (C1)](vm). We can give an e-cut decomposition
from Gm to empty graph by taking Dm as the first e-cut. Combining the above two e-cut
decompositions, we have an e-cut decomposition from G1 to empty graph with |D1| =
|Dm| = 3. By Claim 1, cf(G) ≤ 2c(G) − 2, a contradiction. If Gm is an odd cycle,
by Lemma 2.3, D1 ∪ D2 ∪ · · · ∪ Dm−1 is a complete forcing set of G and cf(G) ≤
X. He and H. Zhang: Complete forcing numbers of graphs 9
c(G) + (m − 1) − c(Gm). Since |D1| = 3 and |Di| ≥ 2 (i = 2, 3, . . . ,m − 1), c(G) −
c(Gm) =
∑m−1
i=1 (|Di| − 1) ≥ m, so we have m ≤ c(G) − c(Gm) = c(G) − 1. Hence,
cf(G) ≤ c(G) + (m− 1)− c(Gm) ≤ 2c(G)− 3, a contradiction.
Claim 3. Each block of G− v1 is either K2 or an even cycle.
Proof. Let B be a block of G − v1. Then dB(v) ≤ 2 for each v ∈ V (B). Otherwise, let
v′ be a vertex of B with dB(v′) = 3. By Lemma 2.2, there exists an e-cut decomposition
from G = G1 to B = Gm by taking D1 = ∂G(v1) as the first e-cut. Let Dm = ∂Gm(v
′).
Then Dm is an e-cut of B and we can give an ED decomposition from B to empty graph
by taking Dm as the first e-cut. Combining with the above two e-cut decompositions, we
have an e-cut decomposition from G to empty graph with |D1| = |Dm| = 3. By Claim 1,
cf(G) ≤ 2c(G) − 2, a contradiction. Since G is a bipartite graph by Claim 2, each block
of G− v1 is K2 or an even cycle.
In the following we may assume that v1 is a black vertex of G.
Claim 4. If each block of G− v1 is K2, then c(G) = 2 and (i) holds.
Proof. Obviously G− v1 is a tree. If G− v1 has no 3-degree vertices, then it is a path P .
Since G is 2-connected, the end-vertices of P are adjacent to v1 and receive white. Further,
since dG(v1) = 3, v1 has third white neighbor as an internal vertex of P (see Figure 2(a)).
So c(G) = 2.
1w 1w
1v
1v
1v
( )a ( )b ( )c
P
Figure 2: Illustration for Claim 4.
If G − v1 has a 3-degree vertex, then G − v1 has only one 3-degree vertex, denoted
by w1. Otherwise, G − v1 has at least four 1-degree vertices, but just three of them is
adjacent to v1 in G, so G has a 1-degree vertex, a contradiction. Thus G − v1 has three
1-degree vertices which are adjacent to v1 in G. It follows that w1 is a white vertex (see
Figure 2(c)); Otherwise, G has an odd number of vertices (see Figure 2(b)), a contradiction.
So c(G) = 2.
In what follows we suppose that G− v1 has a block that is an even cycle.
Claim 5. Each even cycle block of G− v1 has at most two 3-degree vertices in G.
10 Ars Math. Contemp. 23 (2023) #P2.09
C
1
v
3
w
2
w
P
Figure 3: An even cycle block C of G− v1 has exactly three 3-degree vertices of G.
Proof. If G− v1 has an even cycle block that has four 3-degree vertices in G, then it has at
least one end-block that has no vertices that are adjacent to v1 in G. This causes G to have
a cut-vertex, which contradicts that G is 2-connected. If there is an even cycle block C of
G−v1 that has exactly three 3-degree vertices of G, then two of such three vertices w2 and
w3 have the same color in G. Let P be a path contained in C with ends w2 and w3 (see
Figure 3). Then each internal vertex of P is still a 2-degree vertex of G. Further, since G
has an e-cut ∂(V (P )) of four edges, we can give an e-cut decomposition from G to empty
graph by taking ∂(V (P )) as the first e-cut. By Claim 1, we have cf(G) ≤ 2c(G) − 2, a
contradiction.
Claim 6. G− v1 is not 2-connected, and has no vertices contained in three K2 blocks.
P T
1v 1v
4w 4w5w 5w
( )a ( )b
Figure 4: (a) w4 and w5 have the same color; (b) w4 and w5 have different colors.
Proof. If G − v1 is 2-connected, then by Claim 3, G − v1 is an even cycle and v1 is
adjacent to three vertices of this cycle in G, which contradicts Claim 5. So, G − v1 is not
2-connected.
Suppose to the contrary that G − v1 has a vertex w4 incident with three K2 blocks.
Then G−v1 has at least 3 end-blocks. Since G is 2-connected and dG(v1) = 3, G−v1 has
exactly three end-blocks. Let P be a shortest path between w4 and a 3-degree vertex w5 of
G − v1 in an even cycle block so that each internal vertex of P is a 2-degree vertex in G.
If w4 and w5 have the same color, then ∂(V (P )) is an e-cut of G (see Figure 4(a)). There
exists an e-cut decomposition from G to empty graph by taking ∂(V (P )) as the first e-cut.
By Claim 1, we have cf(G) ≤ 2c(G) − 2, a contradiction. If w4 and w5 have different
colors, let T be the tree consisting of P and the remaining two K2 blocks of G − v1 that
X. He and H. Zhang: Complete forcing numbers of graphs 11
has an end-vertex w4. Then ∂(V (T )) is an e-cut of G (see Figure 4(b)). Similarly we have
cf(G) ≤ 2c(G)− 2, a contradiction.
By Claims 3, 5 and 6, G− v1 has exactly two end-blocks which each has a white non-
cut-vertex of G− v1 adjacent to v1 in G, and G− v1 can be constructed as follows: r − 1
disjoint paths P ′1, P
′
2, . . . , P
′
r−1 connect r−2 disjoint even cycles C1, C2, . . . , Cr−2 in turn
so that P ′i only connects Ci−1 and Ci for i = 2, 3, . . . , r − 2, where r ≥ 3, and P ′1 and
P ′r−1 connect only C1 and Cr−2 respectively (see Figure 5(a)). Let v2 be the third neighbor
of v1 in G− v1.
1v
2v
4v
3v
2rC -1C
'
2P
'
1P
'
i
P
'
1rP -
( )a ( )b
Figure 5: (a) The construction of G− v1; (b) Illustration for Claim 7.
Claim 7. v2 must be an internal vertex of paths P ′1 and P ′r−1.
Proof. If v2 belongs to some even cycle Ck (1 ≤ k ≤ r − 2) in G − v1, then Ck has
three 3-degree vertices of G, which contradicts Claim 5. If v2 is an internal vertex of P ′i
(2 ≤ i ≤ r−2) (see Figure 5(b)), let the ends of P ′i be v3 and v4. Then there exists an e-cut
decomposition from G to empty graph by taking ∂(v3) and ∂(v4) as the first two e-cuts.
Since |∂(v3)| = |∂(v4)| = 3, by Claim 1, cf(G) ≤ 2c(G) − 2, a contradiction. Hence v2
is an internal vertex of P ′1 or P
′
r−1 and the claim holds.
1C
i
C
1iC - -1i
C
i
C
+1,1iv
,2iv
,1iv
1C
( )c
'
i
P
'
i
P
,1iv
,2iv
( )a ( )b
2rC -
1rC -
1C
1v
5v
6v
2v
'
2P
'
1P
Figure 6: (a) The construction of G; (b) e-cut (bold edges) leaving from P ′i ; (c) e-cut (bold
edges) leaving from three T .
By Claim 7 we may suppose v2 is an internal vertex of P ′r−1 that has length at least
3. Then the subpath of P ′r−1 between both neighbors of v1 with two incident edges forms
12 Ars Math. Contemp. 23 (2023) #P2.09
a cycle, denoted by Cr−1. Thus G can be constructed from r − 1 disjoint even cycles
C1, C2, . . . , Cr−1 by using r− 1 disjoint paths to connect them in a cyclic way. More pre-
cisely, each P ′i connects vertex vi,1 of Ci−1 and vertex vi,2 of Ci, where i = 1, 2, . . . , r−1
and C0 = Cr−1 (see Figure 6(a)). Note that P ′2, . . . , P
′
r−2 remain unchanged, but P
′
1 is
lengthened by one edge and P ′r−1 is shorten. Then vi,1 and vi,2 have different colors in G.
Otherwise, there exists an e-cut decomposition from G to empty graph by taking ∂(V (P ′i ))
(see Figure 6(b)) as the first e-cut that has four edges. By Claim 1, cf(G) ≤ 2c(G) − 2,
a contradiction. Further, vi,2 and vi+1,1 have different colors in G, where vr,1 = v1,1.
Otherwise, two edges leaving from even cycle Ci are forbidden edges of G, which contra-
dicts that G is matching covered. Finally we claim that vi,2 and vi+1,1 are adjacent in Ci.
Otherwise, since vi,2 and vi+1,1 have different colors, two paths between vi,2 and vi+1,1
in Ci have length at least 3 (see Figure 6(c)). Let v5 and v6 be the two neighbors of vi,2
in Ci. Then v5, v6 and vi,1 are all of the same color in G. Let T be the tree induced by
{v5, v6} ∪ V (P ′i ). Then ∂(V (T )) is an e-cut of G of four edges. So there exists an e-cut
decomposition from G to empty graph by taking ∂(V (T )) as the first e-cut. By Claim 1,
we have cf(G) ≤ 2c(G)− 2, a contradiction.
Let x+P1 be an even cycle formed by the paths P ′i and edges vi,2vi+1,1, i = 1, 2, . . . ,
r − 1, and let Pi+1 be the path between vi,2 and vi+1,1 in Ci of length at least three.
Then the edges vi,2vi+1,1, i = 1, 2, . . . , r − 1, are contained in a frame of x + P1 and
G = x+ P1 + P2 + · · ·+ Pr is an ear decomposition of G described as in (ii).
4 Wheels and cylinders
In this section, we first present some lower bounds on the complete forcing numbers of
some special types of graphs. We then derive some closed formulas for the complete forc-
ing numbers of wheels and cylinders, respectively. Our main idea is to apply an e-cut de-
composition on a given graph to construct a complete forcing set whose cardinality attains
a lower bound on the complete forcing number.
Lemma 4.1. Let G be a graph that admits a perfect matching. If there is a set C of nice
cycles of G such that every edge of G lies in exactly two nice cycles of C, then cf(G) ≥ |C|.
Proof. For a nice cycle C of C, let T1(C) and T2(C) be the two frames of C. Let S be a
minimum complete forcing set of G. By Theorem 2.1, we have
|S ∩ Ti(C)| ≥ 1, i = 1, 2, for each nice cycle C of C.
Summing all the above inequalities together, we have
2|S| =
∑
C∈C
(|S ∩ T1(C)|+ |S ∩ T2(C)|) ≥ 2|C|,
because each edge of S belongs to exactly two nice cycles of C. Then we have
cf(G) = |S| ≥ |C|.
For a plane elementary bipartite graph G, all facial cycles (including the exterior facial
cycle) of G are nice cycles [28]. Since each edge of G lies in exactly two of these facial
cycles, by Lemma 4.1, we have
Corollary 4.2. Let G be a plane elementary bipartite graph with n faces. Then cf(G) ≥ n.
X. He and H. Zhang: Complete forcing numbers of graphs 13
This result is a generalization of a lower bound on the complete forcing numbers of
normal hexagonal systems (see [11]).
A wheel Wn (n ≥ 4) is a graph formed by connecting a single vertex (called the hub) to
all vertices of a cycle (called the rim) with n− 1 vertices. We can check that W2n (n ≥ 2)
is matching covered by the definition.
Theorem 4.3. For n ≥ 2, cf(W2n) = 2n− 1.
Proof. We denote by v0 the hub of W2n and by v1, v2, . . . , v2n−1 the vertices in the
rim of W2n along one of two directions of it. We can see that the set C of 4-cycles
{viv0vi+2vi+1vi|i = 1, 2, . . . , 2n − 1} consisting of 2n − 1 nice cycles of W2n, where
v2n = v1 and v2n+1 = v2. Moreover, each edge of W2n lies in exactly two nice cycles
of C. By Lemma 4.1, cf(W2n) ≥ |C| = 2n − 1. On the other hand, let D1 = ∂W2n(v0).
Then D1 is an e-cut of W2n with 2n − 1 edges. We use D1 to do an e-cut operation on
G1 = W2n and obtain G2. Since G2 is an odd cycle, by Lemma 2.3, D1 is a complete
forcing set. So cf(W2n) ≤ |D1| = 2n− 1. Consequently, cf(W2n) = 2n− 1.
The cartesian product G×H of two graphs G and H is a graph with vertex set V (G)×
V (H) specified by putting (u, v) adjacent to (u′, v′) if and only if (1) u = u′ and vv′ ∈
E(H), or (2) v = v′ and uu′ ∈ E(G). Let Pm = u1u2 · · ·um be a path with m vertices.
Recently, Chang et al. [5] obtained that cf(Pm × Pn) = ⌊n2 ⌋(m − 1) + ⌊
m
2 ⌋(n − 1).
It is natural to consider the complete forcing numbers of m × n cylinders. Let Cn =
v1v2 · · · vnv1 be a cycle with n vertices. An m × n cylinder Pm × Cn consists of m − 1
concentric layers of quadrangles (i.e. each layer is a cyclic chain of n quadrangles), capped
on each end by an n-polygon (see G1 of Figure 7 for an example). If both m and n are
odd, then Pm × Cn has an odd number of vertices and thus has no perfect matchings. So
we only consider the complete forcing number of Pm × Cn with even mn. The operation
of inserting a new vertex of degree two on an edge of a graph is called a subdivision of the
edge.
Lemma 4.4. If m is even, then
cf(Pm × Cn) ≥
{
mn− n2 , if n is even,
2mn+m−n−1
2 , if n is odd.
Proof. For 1 ≤ i ≤ m − 1, let Ri be the subgraph of Pm × Cn induced by {(ui, vj),
(ui+1, vj)| j = 1, 2, . . . , n} and E1i = {(ui, vj)(ui+1, vj)|j = 1, 2, . . . , n}. For 1 ≤ j ≤
n, let Lj be the subgraph of Pm × Cn induced by {(ui, vj), (ui, vj+1)|i = 1, 2, . . . ,m}
and E2j = {(ui, vj)(ui, vj+1)|i = 1, 2, . . . ,m}, where vn+1 = v1. Let S be a minimum
complete forcing set of Pm × Cn. Since Ri has n nice quadrangles of Pm × Cn and
each quadrangle of Ri has a frame completely contained in E1i, by Theorem 1.1, each
quadrangle of Ri has an edge in S ∩E1i. If n is even, then |S ∩E1i| ≥ n2 . And if n is odd,
then |S∩E1i| ≥ n+12 . Since Lj has m−1 nice quadrangles of Pm×Cn and each quadrangle
of Lj has a frame completely contained in E2j , by Theorem 1.1, each quadrangle of Lj
has an edge in S ∩ E2j . Since m is even, |S ∩ E2j | ≥ m2 . Thus we have if n is even, then
cf(Pm ×Cn) = |S| ≥
∑m−1
i=1 |S ∩E1i|+
∑n
j=1 |S ∩E2j | ≥
n(m−1)
2 +
mn
2 = mn−
n
2 .
And if n is odd, then cf(Pm × Cn) = |S| ≥
∑m−1
i=1 |S ∩ E1i| +
∑n
j=1 |S ∩ E2j | ≥
(m−1)(n+1)
2 +
mn
2 =
2mn+m−n−1
2 .
14 Ars Math. Contemp. 23 (2023) #P2.09
Lemma 4.5 (Pick’s theorem [8]). Let P be a simple polygon constructed on a polyomino
such that all the polygon’s vertices are polyomino’s vertices. Let the number of polyomino’s
vertices in the interior of P be i and the number of polyomino’s vertices on the boundary
of P be b. Then the area of P is given by A = b2 + i− 1.
Theorem 4.6.
cf(Pm × Cn) =

mn− n+ 2, if m is odd and n is even (m ≥ 1, n ≥ 4),
mn− n2 , if both m and n are even (m ≥ 2, n ≥ 4),
2mn+m−n−1
2 , if m is even and n is odd (m ≥ 2, n ≥ 3).
Proof. Since mn is even, we can see that each edge of Pm × Cn is allowed, so Pm × Cn
is matching covered. To construct a complete forcing set of Pm × Cn, by Lemma 2.3, we
can directly apply e-cut decomposition on Pm × Cn.
We divide our proof into the following three cases.
Case 1. m is odd and n is even (m ≥ 1, n ≥ 4).
If m = 1, then Pm × Cn is an even cycle and cf(Pm × Cn) = 2 by Theorem 3.1, and
the conclusion holds. In the following, we suppose that m ≥ 3.
By Corollary 4.2, cf(Pm × Cn) ≥ mn− n+ 2. So it suffices to construct a complete
forcing set of Pm × Cn of size mn− n+ 2.
1 1( , )u v
1( , )nu v
1 4( , )u v1 1( , )nu v -
2( , )mu v
1( , )mu v
( , )
m n
u v
( , )
m n
u v
1 2( , )u v
4( , )mu v
2 5( , )u v
1 5( , )mu v-
2 1( , )nu v -
1 1( , )m nu v- -
1G 2G
1( , )nu v
Figure 7: m is odd and n is even.
X. He and H. Zhang: Complete forcing numbers of graphs 15
Let
D1 ={(u2i+1, v1)(u2i+1, v2), (u2i+1, v2)(u2i+1, v3) | i = 0, 1, 2, . . . ,
m− 1
2
}∪
{(uj , v1)(uj+1, v1), (uj , v3)(uj+1, v3) | j = 1, 2, . . . ,m− 1}∪
{(u2k, vn)(u2k, v1), (u2k, v3)(u2k, v4) | k = 1, 2, . . . ,
m− 1
2
}
(see bold edges of G1 of Figure 7). Then D1 is an e-cut of G1 = Pm × Cn. We
use D1 to do an ED operation on G1 and obtain G2 = Pm × Pn−3 (see Figure 7).
Let D2, D3, . . . , D (m−1)(n−4)
4 +1
be ∂G2((u2i, v5)), ∂G2((u2i, v7)),. . . , ∂G2((u2i, vn−1))
(i = 1, 2, . . . , m−12 ), respectively. Then we continue to do ED operations from G2 by
D2, D3, . . . , D (m−1)(n−4)
4 +1
in turn and obtain G (m−1)(n−4)
4 +2
. Note that Di is an e-cut
of Gi for i = 1, 2, . . . ,
(m−1)(n−4)
4 + 1. We find that G (m−1)(n−4)
4 +2
can be obtained by
subdividing every edge of Pm−1
2 +1
× Pn−4
2 +1
as shown in the thin edges of G2 in Fig-
ure 7. Let C be a cycle of G (m−1)(n−4)
4 +2
. Suppose that C encloses some region R in
the plane, let A be the area of R, b be the number of vertices of G2 on C, and i be the
number of vertices of G2 in the interior of C. Then A is divisible by 4. We can see that
C is obtained by subdividing every edge of a cycle C ′ of Pm−1
2 +1
× Pn−4
2 +1
. Since C ′
is a cycle of even length and |V (C)| = 2|V (C ′)|, b is divisible by 4. By Lemma 4.5, i is
odd. Then G1 − V (C) has no perfect matchings. So each cycle of G (m−1)(n−4)
4 +2
is not
a nice cycle of G1. By Lemma 2.3, D1 ∪ D2 ∪ . . . D (m−1)(n−4)
4 +1
is a complete forcing
set of G1. Since |D1| = (m + 1) + 2(m − 1) + (m − 1) = 4m − 2 and |Di| = 4 for
i = 2, 3, . . . , (m−1)(n−4)4 + 1, cf(G1) ≤ |D1 ∪D2 ∪ . . . D (m−1)(n−4)
4 +1
| = mn− n+ 2.
Consequently, cf(Pm × Cn) = mn− n+ 2.
Case 2. Both m and n are even (m ≥ 2, n ≥ 4).
By Lemma 4.4, it suffices to construct a complete forcing set of Pm × Cn of size
mn− n2 . Let
D1 ={(u2i+1, v1)(u2i+1, v2), (u2i+1, v2)(u2i+1, v3) | i = 0, 1, 2, . . . ,
m− 2
2
}∪
{(uj , v1)(uj+1, v1), (uj , v3)(uj+1, v3) | j = 1, 2, . . . ,m− 1)}∪
{(u2k, vn)(u2k, v1), (u2k, v3)(u2k, v4) | k = 1, 2, . . . ,
m
2
}.
Then D1 is an e-cut of G1 = Pm × Cn. We use D1 to do an ED operation on G1 =
Pm × Cn and obtain G2 = Pm × Pn−3 (see Figure 8). Let D2, D3, . . . , Dm(n−4)
4 +1
be ∂G2((u2i, v5)), ∂G2((u2i, v7)),. . . , ∂G2((u2i, vn−1)) (i = 1, 2, . . . ,
m
2 ), respectively.
Continuously doing ED operations from G2 by D2, D3, . . . , Dm(n−4)
4 +1
in turn, we obtain
Gm(n−4)
4 +2
. Note that Gm(n−4)
4 +2
can be obtained by subdividing every edge of Pm−2
2 +1
×
Pn−4
2 +1
as shown in Figure 8. Let C be a cycle of Gm(n−4)
4 +2
. Suppose that C encloses
some region R in the plane, let A be the area of R, b the number of vertices of G2 on C, and
i be the number of vertices of G2 in the interior of C. Then A is divisible by 4. We can see
that C is obtained by subdividing every edge of a cycle C ′ of Pm−2
2 +1
×Pn−4
2 +1
. Since C ′
is a cycle of even length and |V (C)| = 2|V (C ′)|, b is divisible by 4. By Lemma 4.5, i is
16 Ars Math. Contemp. 23 (2023) #P2.09
1 1( , )u v
1( , )nu v
1 4( , )u v1 1( , )nu v -
2( , )mu v
1( , )mu v
( , )
m n
u v
( , )
m n
u v
1 2( , )u v
4( , )mu v
2 5( , )u v
5( , )mu v
2 1( , )nu v -
1( , )m nu v -
1G 2G ( 4) 2
4
m n
G
-
+
1( , )nu v
Figure 8: Both m and n are even.
odd. So G1 − V (C) has no perfect matchings. Thus each cycle of Gm(n−4)
4 +2
is not a nice
cycle of G1. By Lemma 2.3, D1 ∪ D2 ∪ . . . Dm(n−4)
4 +1
is a complete forcing set of G1.
Since |D1| = m + 2(m − 1) +m = 4m − 2, |Di| = 4 for i = 2, 3, . . . , (m−2)(n−4)4 + 1
and |Dj | = 3 for j = (m−2)(n−4)4 + 2,
(m−2)(n−4)
4 + 3, . . . ,
m(n−4)
4 + 1, cf(G1) ≤
|D1 ∪D2 ∪ . . . D (m−1)(n−4)
4 +1
| = mn− n2 . Consequently, cf(Pm × Cn) = mn−
n
2 .
Case 3. m is even and n is odd (m ≥ 2, n ≥ 3).
By Lemma 4.4, it suffices to prove cf(G1) ≤ 2mn+m−n−12 .
2( , )mu v 2( , )mu v
1 2( , )u v
3( , )mu v 3( , )mu v
1( , )mu v
1( , )mu v
1 1( , )u v
2 3( , )u v
2 2( , )u v 2 1( , )u v
1 3( , )u v
( )a ( )b
1D
m
D
1
2
m
D
+
2
m
D
Figure 9: m is even and n = 3.
X. He and H. Zhang: Complete forcing numbers of graphs 17
Subcase 3.1. n = 3.
Let G1 = Pm × C3 and D1, D2, . . . , Dm2 be ∂G1((u2i+1, v3)) (i = 0, 1, . . . ,
m−2
2 ),
respectively (see Figure 9(a)). Then we use D1, D2, . . . , Dm2 to do ED operations on
G1 in turn and obtain Gm2 +1. Let Dm2 +1, Dm2 +2, . . . , Dm be ∂Gm2 +1((u2i+1, v2)) (i =
0, 1, . . . , m−22 ), respectively. Then we use Dm2 +1, Dm2 +2, . . . , Dm to do ED operations in
turn and obtain Gm+1. We can see that Gm+1 consists of m2 disjoint cycles of length 3 and
c(Gm+1) =
m
2 as shown in Figure 9(b). Thus each cycle of Gm+1 is not a nice cycle of
G1. By Lemma 2.3, cf(G1) ≤ c(G1)+m−c(Gm+1) = 3(m−1)+1+m− m2 =
7m−4
2 .
Consequently, cf(Pm × C2n) = 7m−42 .
1 4( , )u v1( , )nu v
4( , )mu v( , )m nu v
1G 2G
1( , )nu v
( , )
m n
u v
1( , )mu v
2( , )mu v
2D
1
2
m
D
+
3
2 2
m n
D
-
+
Figure 10: m is even and n is odd (n ≥ 5).
Subcase 3.2. n ≥ 5.
Let
D1 ={(u2i+1, v1)(u2i+1, v2), (u2i+1, v2)(u2i+1, v3) | i = 0, 1, 2, . . . ,
m− 2
2
)}∪
{(uj , v1)(uj+1, v1), (uj , v3)(uj+1, v3)|j = 1, 2, . . . ,m− 1}∪
{(u2k, vn)(u2k, v1), (u2k, v3)(u2k, v4)|k = 1, 2, . . . ,
m
2
}.
Then we use D1 to do an ED operation on G1 = Pm × C2n and obtain G2 =
Pm × Pn−3 (see Figure 10). Let Dt (t = 2, 3, . . . , m2 ) be
{(u2t−2, v2i+2)(u2t−1, v2i+2) | i = 1, 2, . . . ,
n− 3
2
}∪
{(u2t−2, vj+3)(u2t−2, vj+4) | j = 1, 2, . . . , n− 4}∪
{(u2t−3, v2k+3)(u2t−2, v2k+3) | k = 1, 2, . . . ,
n− 3
2
}.
18 Ars Math. Contemp. 23 (2023) #P2.09
Then we use D2, D3, . . . , Dm2 to do ED operations on G1 in turn and obtain Gm2 +1 which
is P2 × Pn−3. Let Dm2 +1, Dm2 +2, . . . , Dm2 +n−32 be ∂Gm2 +1((um, v2s+3))
(s = 1, 2, . . . , n−32 ), respectively. Then we use Dm2 +1, Dm2 +2, . . . , Dm2 +n−32 to do ED op-
erations on Gm
2 +1
in turn and obtain Gm
2 +
n−3
2 +1
which is the empty graph. By Lemma 2.3,
D1 ∪D2 ∪ · · · ∪Dm
2 +
n−3
2
is a complete forcing set of G1 and cf(G1) ≤ c(G1) + m2 +
n−3
2 − 0 =
2mn+m−n−1
2 . Consequently, cf(Pm × Cn) =
2mn+m−n−1
2 .
At the end of this paper, by some simple calculations, we present the relationship
between the cyclomatic number and complete forcing number for wheels and cylinders.
For a wheel W2n, c(W2n) = |E(W2n)| − |V (W2n)| + 1 = 2(2n − 1) − 2n + 1 =
2n − 1. By Theorem 4.3, cf(W2n) = c(W2n). For a cylinder Pm × Cn, c(Pm × Cn) =
|E(Pm × Cn)| − |V (Pm × Cn)| + 1 = n(m − 1) +mn −mn + 1 = mn − n + 1. By
Theorem 4.6, we can see that cf(Pm ×Cn) = c(Pm ×Cn) + 1 if m is odd and n is even,
cf(Pm × Cn) = c(Pm × Cn) + n2 − 1 if both m and n are even, and cf(Pm × Cn) =
c(Pm × Cn) + m+n−32 if m is even and n is odd.
ORCID iDs
Xin He https://orcid.org/0000-0002-5853-9653
Heping Zhang https://orcid.org/0000-0001-5385-6687
References
[1] H. Abeledo and G. W. Atkinson, A min-max theorem for plane bipartite graphs, Discrete
Appl. Math. 158 (2010), 375–378, doi:10.1016/j.dam.2009.11.004, http://doi.org/10.
1016/j.dam.2009.11.004.
[2] J. Bondy and U. Murty, Graph Theory with Applications, American Elsevier, New York,
Macmillan, London,, 1976, https://link.springer.com/book/9781846289699.
[3] J. Cai and H. Zhang, Global forcing number of some chemical graphs, MATCH Commun. Math.
Comput. Chem. 67 (2012), 289–312, https://match.pmf.kg.ac.rs/electronic_
versions/Match67/n2/match67n2_289-312.pdf.
[4] W. H. Chan, S.-J. Xu and G. Nong, A linear-time algorithm for computing the complete forcing
number and the Clar number of catacondensed hexagonal systems, MATCH Commun. Math.
Comput. Chem. 74 (2015), 201–216, https://match.pmf.kg.ac.rs/electronic_
versions/Match74/n1/match74n1_201-216.pdf.
[5] H. Chang, Y.-D. Feng, H. Bian and S.-J. Xu, Complete forcing numbers of rectangular poly-
nominoes, Acta Math. Spalatensia 1 (2021), 87–96, doi:10.32817/ams.1.1.7, http://doi.
org/10.32817/ams.1.1.7.
[6] Z. Che and Z. Chen, Forcing on perfect matchings - a survey, MATCH Commun. Math.
Comput. Chem. 66 (2011), 93–136, https://match.pmf.kg.ac.rs/electronic_
versions/Match66/n1/match66n1_93-136.pdf.
[7] T. Došlić, Global forcing number of benzenoid graphs, J. Math. Chem. 41 (2007), 217–229, doi:
10.1007/s10910-006-9056-2, http://doi.org/10.1007/s10910-006-9056-2.
[8] B. Grünbaum and G. C. Shephard, Pick’s theorem, Am. Math. Mon. 100 (1993), 150–161,
doi:10.2307/2323771, http://doi.org/10.2307/2323771.
X. He and H. Zhang: Complete forcing numbers of graphs 19
[9] X. Guo and F. Zhang, k-cycle resonant graphs, Discrete Math. 135 (1994), 113–120,
doi:10.1016/0012-365x(93)e0086-j, http://doi.org/10.1016/0012-365x(93)
e0086-j.
[10] P. Hansen and M. Zheng, The Clar number of a benzenoid hydrocarbon and linear program-
ming, J. Math. Chem. 15 (1994), 93–107, doi:10.1007/bf01277551, http://doi.org/10.
1007/bf01277551.
[11] X. He and H. Zhang, Complete forcing numbers of hexagonal systems, J. Math. Chem.
59 (2021), 1767–1784, doi:10.1007/s10910-021-01261-3, http://doi.org/10.1007/
s10910-021-01261-3.
[12] X. He and H. Zhang, Complete forcing numbers of hexagonal systems. II, J. Math. Chem.
60 (2022), 666–680, doi:10.1007/s10910-022-01330-1, http://doi.org/10.1007/
s10910-022-01330-1.
[13] W. C. Herndon, Resonance theory and the enumeration of kekulé structures, J. Chem. Educ. 51
(1974), 10–15, doi:10.1021/ed051p10, http://doi.org/10.1021/ed051p10.
[14] H. Lei, Y.-N. Yeh and H. Zhang, Anti-forcing numbers of perfect matchings of graphs, Discrete
Appl. Math. 202 (2016), 95–105, doi:10.1016/j.dam.2015.08.024, http://doi.org/10.
1016/j.dam.2015.08.024.
[15] B. Liu, H. Bian and H. Yu, Complete forcing numbers of polyphenyl systems, Iran. J. Math.
Chem. 7 (2016), 39–46, doi:10.22052/ijmc.2016.11868, http://doi.org/10.22052/
ijmc.2016.11868.
[16] B. Liu, H. Bian, H. Yu and J. Li, Complete forcing numbers of spiro hexagonal systems,
Polyc. Arom. Comp. 41 (2021), 511–517, doi:10.1080/10406638.2019.1600560, http://
doi.org/10.1080/10406638.2019.1600560.
[17] L. Lovász and M. D. Plummer, Matching Theory, volume 29 of Ann. Discrete Math., Elsevier,
Amsterdam, 1986.
[18] M. D. Plummer, On n-extendable graphs, Discrete Math. 31 (1980), 201–210, doi:10.1016/
0012-365x(80)90037-0, http://doi.org/10.1016/0012-365x(80)90037-0.
[19] H. Sachs, Perfect matchings in hexagonal systems, Combinatorica 4 (1984), 89–99, doi:10.
1007/bf02579161, http://doi.org/10.1007/bf02579161.
[20] J. Sedlar, The global forcing number of the parallelogram polyhex, Discrete Appl. Math.
160 (2012), 2306–2313, doi:10.1016/j.dam.2012.05.021, http://doi.org/10.1016/
j.dam.2012.05.021.
[21] D. Vukičević and T. Došlić, Global forcing number of grid graphs, Australas. J. Comb. 38
(2007), 47–62, https://ajc.maths.uq.edu.au/pdf/38/ajc_v38_p047.pdf.
[22] D. Vukičević and J. Sedlar, Total forcing number of the triangular grid, Math. Commun. 9
(2004), 169–179.
[23] S.-J. Xu, X.-S. Liu, W. H. Chan and H. Zhang, Complete forcing numbers of primitive
coronoids, J. Comb. Optim. 32 (2016), 318–330, doi:10.1007/s10878-015-9881-y, http:
//doi.org/10.1007/s10878-015-9881-y.
[24] S.-J. Xu, H. Zhang and J. Cai, Complete forcing numbers of catacondensed hexagonal systems,
J. Comb. Optim. 29 (2015), 803–814, doi:10.1007/s10878-013-9624-x, http://doi.org/
10.1007/s10878-013-9624-x.
[25] F. Zhang and R. Chen, When each hexagon of a hexagonal system covers it, Discrete
Appl. Math. 30 (1991), 63–75, doi:10.1016/0166-218x(91)90014-n, http://doi.org/
10.1016/0166-218x(91)90014-n.
20 Ars Math. Contemp. 23 (2023) #P2.09
[26] F. Zhang, R. Chen and X. Guo, Perfect matchings in hexagonal systems, Graphs Comb. 1
(1985), 383–386, doi:10.1007/bf02582965, http://doi.org/10.1007/bf02582965.
[27] H. Zhang and J. Cai, On the global forcing number of hexagonal systems, Discrete Appl. Math.
162 (2014), 334–347, doi:10.1016/j.dam.2013.08.020, http://doi.org/10.1016/j.
dam.2013.08.020.
[28] H. Zhang and F. Zhang, Plane elementary bipartite graphs, Discrete Appl. Math. 105
(2000), 291–311, doi:10.1016/s0166-218x(00)00204-3, http://doi.org/10.1016/
s0166-218x(00)00204-3.