关键词: 单圈图, 零强迫, 全强迫, 匹配

Abstract:

Let $S\subseteq V$ be an initial vertex subset of coloring, and all vertices of $S\subseteq V$ are black. Each vertex in $S$ is called $S$-colored, and all other vertices in $G$ are called $S$-uncolored. If a vertex $v$ with black color has just one uncolored neighbor $u$, then $v$ forces the vertex $u$ to be black. Such a process is called forcing process. The initial set $S$ is called a zero forcing set (forcing set) of $G$ if, by iteratively applying the forcing process, every vertex in $G$ becomes black. The minimum cardinality of a zero forcing set in $G$ is zero forcing number, denoted $F(G)$. If the induced subgraph $G[S]$ does not contain isolated vertices, then $S$ is called a total forcing set of $G$, and the minimum cardinality of a total forcing set in $G$ is total forcing number, denoted $F_t(G)$. Note that zero forcing number and total forcing number of graph $G$ has the relation, $F(G)\leq F_t (G)\leq 2F(G)$. Hence, it is interesting and meaningful to characterize all graphs satisfying $F(G)=F_t (G)$ or $2F(G)=F_t (G)$. In this paper, we study all graphs $G$ satisfying $F(G)=F_t (G)$ in unicyclic graphs. In addition, we discuss the upper bound of zero forcing number in all unicyclic graphs with given matching number $k$, and show that $F(G)\leq n-k$ and equality holds if and only if $G\cong C_4, A_0$. Moreover, we characterize all graphs such that their forcing number equal to $n-k-1$ if $G\not\cong C_4, A_0$.

Key words: unicyclic graph, zero forcing, total forcing, matching