山东理工大学数学与统计学院，山东 淄博

收稿日期：2023年3月26日；录用日期：2023年4月21日；发布日期：2023年4月28日

摘要

设F(G)是图G的零强迫数，gp(G)是图G的一般位置数。注意， $gp\left(G\right)\ge F\left(T\right)+1$ 对所有树T都成立。Hua等人在中证明了此结果可以扩展到块图，并证明了对于连通单圈图G， $gp\left(G\right)\ge F\left(T\right)$ 。在本文中，我们刻画了使得 $gp\left(G\right)\ge F\left(T\right)$ 成立的双圈图的结构。

关键词

零强迫数，一般位置数，双圈图

Zero Forcing Number and General Position Number in Bicyclic Graphs

Yu Jing

School of Mathematics and Statistics, Shandong University of Technology, Zibo Shandong

Received: Mar. 26^th, 2023; accepted: Apr. 21^st, 2023; published: Apr. 28^th, 2023

ABSTRACT

Let F(G) be the zero forcing number of G and gp(G) be the general position number of G. Note that $gp\left(T\right)\ge F\left(T\right)+1$ holds for any tree T. Hua et al. showed that this result can be extended to block graphs, and showed that $gp\left(G\right)\ge F\left(G\right)$ for connected unicyclic graphs. In this paper, we characterize the structure of bicyclic graphs satisfying $gp\left(G\right)\ge F\left(G\right)$ .

Keywords:Zero Forcing Number, General Position Number, Bicyclic Graph

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

设 $G=\left(V\left(G\right),E\left(G\right)\right)$ 是一个阶为n(G)且边数为m(G)的有限简单图。设 $c\left(G\right)=m\left(G\right)-n\left(G\right)+1$ 是图G的基本圈数。显然，如果 $c\left(G\right)=0$ ，则G是树，如果 $c\left(G\right)=1$ ，则G是单圈图，如果 $c\left(G\right)=2$ ，那么G是双圈图。设 $S\subseteq V\left(G\right)$ 是一个初始着色顶点子集，它的所有顶点都着黑色，若一个黑色的顶点v恰好只有一个未着色的邻点u，则v强迫顶点u着黑色，按照这样的着色规则使得G的所有顶点都变成黑色，则称初始集S为G的一个零强迫集。G的零强迫集的最小基数称为G的零强迫数，用F(G)表示。图的零强迫数的概念首次在2008年AIM Minimum Rank-Special Graphs Work Group提出( [1] )，学者们用它来界定图矩阵的最小秩和最大零秩(见 [2] [3] [4] )。在 [5] 中，Montazeri和Soltankhah讨论了零强迫数与路覆盖数之间的关系，并用路覆盖数来界定零强迫数。在 [6] 中，Davila和Kenter猜想，对最大度Δ至少为2的连通图G，当且仅当 $G=C_n,G=K_{\Delta +1}$ 或 $G=K_{\Delta ,\Delta }$ 时，图G的零强迫数等于 $\left(\Delta -2\right)n+2/\Delta -1$ 。随后，Gentner等人和Lu等人分别证明了此猜想( [7] [8] )。学者们还研究了树的零强迫数并用不同的图参数来界定零强迫数(见 [9] [10] [11] )。

连通图G中的两个顶点u和v的距离是指图G中最短的uv-路的长度，记为 $d_G\left(x,y\right)$ ，或者简记为 $d\left(x,y\right)$ 。如果 $d_G\left(v\right)=1$ ，顶点v称为图G的一个悬挂顶点，对于任意树T，其悬挂顶点也可称为叶子点，并且树T的叶子点数(悬挂顶点数)记为p(T)。G的一个顶点u的度是指它的邻点数，记为 $d_G\left(u\right)$ (或简记为d(u))。记图G中任意导出圈C的最大直径为dp(C)。如果一条路P的内部顶点全是2度顶点，则称P是一条简单路。

设C是图G的一个圈， $v\in V\left(C\right)$ ，若v的邻点有不在G的任意圈上的顶点，则称V是G的圈C上的一个分叉顶点。对于圈C上的分叉顶点u，称T(u)为分叉顶点u的导出树，并且对T(u)的任意顶点 $v\ne u$ ，显然有 $v\notin V\left(C\right)$ 。方便起见，在本文中提到的T(u)的悬挂顶点特指除u以外的T(u)的悬挂顶点。

对于图G的一个顶点子集R，如果在R中任意三个顶点不在同一条最短路上，则称R是G的一个一般位置集。图G的一般位置数gp(G)是G的最大一般位置集的顶点数。图的一般位置数在 [5] 中被提出，随后，在 [12] 中图的一般位置集被刻画。边一般位置集也在 [13] 中被学者们研究。对于任意树T， $gp\left(G\right)\ge F\left(G\right)+1$ 都成立。在 [14] 中，Hua等人证明了 $gp\left(G\right)\ge F\left(G\right)$ 在连通单圈图中成立，并提出问题双圈图满足什么结构时 $gp\left(G\right)\ge F\left(G\right)$ 成立？受这篇文章的启发，我们研究了这个问题。在本文中，我们找到了使得 $gp\left(G\right)\ge F\left(G\right)$ 成立的双圈图的结构。

2. 主要结果

在给出主要结果之前，我们首先介绍一些基本结果和符号。在 [9] 中，张文前等人研究了树的零强迫数，并用树的悬挂顶点数来界定零强迫数，得到树的零强迫数的上界。

引理1： [9] 若T是树，则 $F\left(T\right)\ge p\left(T\right)-1$ 。

也就是说，对于任意树T，选取 $p\left(T\right)-1$ 个悬挂顶点即可构成T的一个零强迫集。而在双圈图G上，若 $u\in V\left(G\right)$ 是图G圈上的一个分叉顶点，设 $S_1\subseteq V\left(G\right)$ ，在颜色变化过程中，S₁使得G中除了V(T(u))以外的所有顶点都被着黑，此时可应用此引理寻找T(u)中除u以外的悬挂顶点作为T(u)的一个零强迫集S₂，显然， $S_1\cup S_2$ 是图G的一个零强迫集。

对于任意连通图G，显然满足以下结论。

引理2：设G是连通图，则 $gp\left(G\right)\ge \left|L\right|$ ，其中L是图G的悬挂顶点集合。

定义 $\mathcal{A}$ 为双圈图的族，即，对任意连通图G，若 $G\in \mathcal{A}$ ，则G是双圈图。

根据双圈图的结构性质，双圈图一定包含以下结构之一(如图1所示)。

图1. 双圈图的三种结构

结构 ${\alpha }_1$ ：双圈图的两个圈没有交点；

结构 ${\alpha }_2$ ：双圈图的两个圈恰好有一个交点；

结构 ${\alpha }_3$ ：双圈图的两个圈至少有一条公共边。

如上图所示，双圈图的两个圈之间的公共交点称为交叉顶点并分别用s和t表示(结构 ${\alpha }_2$ 只有一个交点s)。特别地，结构 ${\alpha }_1$ 中有唯一的一条路P_st，它的两端点s，t分别位于两个不同圈上，我们称这条路上除端点s和t的度至少为3的顶点为分叉顶点，并称路P_st与两个圈的交点为交叉顶点。

方便起见，我们按位置将分叉顶点划分为以下部分： $B_1,B_2,B_3,B_p,B_s,B_t$ (如图2(a)~(c)所示，并且忽略分叉顶点及其导出树)，并记对应的圈和路为 $C_1,C_2,P_1,P_2,P_3$ 和 $P_{st}$ (如图2(d)~(f)所示)，对应分叉顶点的导出树的悬挂顶点数记为 ${\mathcal{l}}_{C_1},{\mathcal{l}}_{C_2},{\mathcal{l}}_{P_1},{\mathcal{l}}_{P_2},{\mathcal{l}}_{P_3},{\mathcal{l}}_{st}$ ，并将交点处悬挂路的顶点数记为 ${\mathcal{l}}_s$ 和 ${\mathcal{l}}_t$ (即，T(s)和T(t)的悬挂顶点数) (如图2(g)~(i)所示)。注意，对任意 $i=1,2$ ， $j=1,2,3$ ， ${\mathcal{l}}_{C_i}$ 和 ${\mathcal{l}}_{P_j}$ 不包含s和t的悬挂顶点数。将双圈图G中所有悬挂顶点集合记为L，并且 $\left|L\right|=\mathcal{l}$ 。

图2. 双圈图的顶点划分

若 $G\in \mathcal{A}$ ，定义一类双圈图族 $\mathcal{B}$ ，若 $G\in \mathcal{B}$ ，则G包含以下结构之一。

结构 ${\beta }_1$ ：双圈图的两个圈至多有一个交点且 $\left|V\left(C_1\right)\right|\ge 3$ ， $\left|V\left(C_2\right)\right|\ge 4$ ， ${\mathcal{l}}_{C_1}\ne 0$ ， ${\mathcal{l}}_{C_2}\ne 0$ 。

结构 ${\beta }_2$ ：双圈图的两个圈至少有两条公共边， $\left|V\left(P_1\right)\right|\ge 3$ ， $\left|V\left(P_2\right)\right|\ge 3$ ， $\left|V\left(P_3\right)\right|\ge 4$ ， ${\mathcal{l}}_{P_1}={\mathcal{l}}_{P_2}={\mathcal{l}}_{P_3}=0$ 且 ${\mathcal{l}}_s,{\mathcal{l}}_t\ge 3$ 或者至少有一个 ${\mathcal{l}}_{P_i}$ 不为0( $i=1,2,3$ )。

结构 ${\beta }_3$ ：双圈图的两个圈至少有两条公共边， $\left|V\left(P_1\right)\right|=\left|V\left(P_2\right)\right|=\left|V\left(P_3\right)\right|=3$ ， ${\mathcal{l}}_{P_1}={\mathcal{l}}_{P_2}={\mathcal{l}}_{P_3}=0$ 且 ${\mathcal{l}}_s,{\mathcal{l}}_t\ge 3$ 或者 ${\mathcal{l}}_{P_i}\ne 0$ ， ${\mathcal{l}}_{P_j}={\mathcal{l}}_{P_k}=0$ ( $i,j,k=1,2,3$ 并且 $i\ne j\ne k$ )。

定理3：设 $G\in \mathcal{A}\backslash \mathcal{B}$ ，则

$gp\left(G\right)\ge F\left(G\right)$ (1)

通过零强迫数的性质和一般位置数的性质，易得到以下结论。

引理4：若 $G\in \mathcal{A}$ 包含结构 ${\alpha }_1$ ，并且 $G\notin \mathcal{B}$ ，则 $gp\left(G\right)\ge F\left(G\right)$ 。

证明：设 $G\in \mathcal{A}$ 包含结构 ${\alpha }_1$ ，按照双圈图中圈的长度，我们首先分两种情况进行讨论，再根据C₁，C₂上是否存在分叉顶点分为几种子情况进行讨论。

情形1： $\left|V\left(C_1\right)\right|\ge 3$ 并且 $\left|V\left(C_2\right)\right|\ge 4$ 。

情形1.1：如果 ${\mathcal{l}}_{C_1}={\mathcal{l}}_{C_2}=0$ ，选择两个相邻顶点 $\left\{u,v\right\}\in V\left(C_1\right)\backslash \left\{s\right\}$ 和t的一个邻点 $w\in V\left(C_2\right)$ ，那么 $\left\{u,v,w\right\}$ 和所有的悬挂顶点构成G的一个零强迫集，则有 $F\left(G\right)\le \mathcal{l}+\left|\left\{u,v,w\right\}\right|=\mathcal{l}+3$ 。选择四个顶点 $\left\{x,y\right\}\in V\left(C_1\right)$ ， $\left\{m,n\right\}\in V\left(C_2\right)$ 满足 $d\left(x,y\right)=dp\left(C_1\right)$ ， $d\left(m,n\right)=dp\left(C_2\right)$ ，并且 $\left|d\left(x,s\right)-d\left(y,s\right)\right|\le 1$ ， $\left|d\left(m,t\right)-d\left(n,t\right)\right|\le 1$ ，那么G的所有悬挂顶点和 $\left\{x,y,m,n\right\}$ 构成G的一个一般位置集，那么 $gp\left(G\right)\ge \mathcal{l}+\left|\left\{x,y,m,n\right\}\right|=\mathcal{l}+4$ 。显然 $F\left(G\right)\le gp\left(G\right)$ 。

情形1.2：如果 ${\mathcal{l}}_{C_1}=0$ ， ${\mathcal{l}}_{C_2}\ne 0$ (或者 ${\mathcal{l}}_{C_2}=0$ ， ${\mathcal{l}}_{C_1}\ne 0$ )，选择s的一个邻点 $u\in V\left(C_1\right)$ 和C₂中一个分叉顶点的邻点 $w\in V\left(C_2\right)$ ， $\left\{u,w\right\}$ 和G的所有的悬挂顶点构成G的一个零强迫集，可得 $F\left(G\right)\le \mathcal{l}+2$ 。选择两个顶点 $x,y\in V\left(C_1\right)$ ， $d\left(x,y\right)=dp\left(C_1\right)$ 并且 $\left|d\left(x,s\right)-d\left(y,s\right)\right|\le 1$ ，那么G的所有悬挂顶点和 $\left\{x,y\right\}$ 构成G的一个一般位置集，那么有 $gp\left(G\right)\ge \mathcal{l}+\left|\left\{x,y\right\}\right|=\mathcal{l}+2\ge F\left(G\right)$ (如图3所示)。

图3. ${\mathcal{l}}_{C_1}=0$ ， ${\mathcal{l}}_{C_2}\ne 0$

情形1.3：如果 ${\mathcal{l}}_{C_1}\ne 0$ 并且 ${\mathcal{l}}_{C_2}\ne 0$ 。设v是C₁的一个分叉顶点并且 $u\in V\left(C_1\right)\backslash \left\{s\right\}$ 是它的一个邻点， $w\in V\left(C_2\right)$ 是t的一个邻点，那么 $\left\{u,w\right\}$ 和除一个外所有的悬挂顶点构成G的一个零强迫数，并且 $F\left(G\right)\le \mathcal{l}-1+\left|\left\{u,w\right\}\right|=\mathcal{l}+1$ 。G的所有悬挂顶点构成G的一个一般位置集，那么 $gp\left(G\right)\ge \mathcal{l}$ (如图4所示)。然而，这时不能得到不等式(1)。

情形2： $\left|V\left(C_1\right)\right|=\left|V\left(C_2\right)\right|=3$ 。

设 $\left\{u,v\right\}\in V\left(C_1\right)$ 和 $\left\{w,x\right\}\in V\left(C_2\right)$ 分别是顶点s和t的邻点。分下面三种子情况讨论。

情形2.1：如果 ${\mathcal{l}}_{C_1}={\mathcal{l}}_{C_2}=0$ ，则 $\left\{u,v,w\right\}$ 和所有的悬挂顶点构成G的一个零强迫集， $\left\{u,v,w,x\right\}$ 和所有悬挂顶点为G的一个一般位置集，那么可得 $F\left(G\right)\le \mathcal{l}+3<\mathcal{l}+4\le gp\left(G\right)$ 。

图4. ${\mathcal{l}}_{C_1}\ne 0$ ， ${\mathcal{l}}_{C_2}\ne 0$

情形2.2：如果 ${\mathcal{l}}_{C_1}=0$ ， ${\mathcal{l}}_{C_2}\ne 0$ (或者 ${\mathcal{l}}_{C_2}=0$ ， ${\mathcal{l}}_{C_1}\ne 0$ )，则 $\left\{w,x\right\}$ 中至少有一个分叉顶点，不失一般性，假设x为分叉顶点，那么 $\left\{u,w\right\}$ 和所有悬挂顶点构成G的一个零强迫集同时也构成G的一个一般位置集，那么可得 $F\left(G\right)\le \mathcal{l}+2\le gp\left(G\right)$ 。

情形2.3：如果 ${\mathcal{l}}_{C_1}\ne 0$ 并且 ${\mathcal{l}}_{C_2}\ne 0$ 。我们考虑 $\left\{u,v,w,x\right\}$ 中的分支顶点数。当恰好有一个分叉顶点在 $C_i\left(i=1,2\right)$ 中时，不失一般性，设u，w是分叉顶点，那么v和所有悬挂顶点构成一个零强迫集，而 $\left\{v,x\right\}$ 和所有悬挂顶点构成G的一个一般位置集，可得 $F\left(G\right)\le \mathcal{l}+1<\mathcal{l}+2\le gp\left(G\right)$ (如图5所示)；当 $\left\{u,v,w,x\right\}$ 中恰好只有一个不是分叉顶点时，不失一般性，假设x不是分叉顶点，那么 和所有悬挂顶点构成G的一个一般位置集，而所有悬挂顶点构成G的一个零强迫集，可得 $F\left(G\right)\le \mathcal{l}<\mathcal{l}+1\le gp\left(G\right)$ ；当 $\left\{u,v,w,x\right\}$ 都是分叉顶点时，所有悬挂顶点构成G的一个一般位置集，而除一个外所有悬挂顶点构成G的一个零强迫集，可得 $F\left(G\right)\le \mathcal{l}-1<\mathcal{l}\le gp\left(G\right)$ 。

图5. ${\mathcal{l}}_{C_1}\ne 0$ ， ${\mathcal{l}}_{C_2}\ne 0$ 且 $u,w$ 为分叉顶点

综上，当 $G\in \mathcal{A}$ 包含结构 ${\alpha }_1$ ，并且 $G\notin \mathcal{B}$ 时， $gp\left(G\right)\ge F\left(G\right)$ 。证明完成。

引理5：若 $G\in \mathcal{A}$ 包含结构 ${\alpha }_2$ ，并且 $G\notin \mathcal{B}$ ，则 $gp\left(G\right)\ge F\left(G\right)$ 。

证明：设 $G\in \mathcal{A}$ 包含结构 ${\alpha }_2$ ，我们首先根据双圈图中两个圈的圈长分下面两种情况进行讨论，再根据C₁，C₂上是否存在分叉顶点进行分类讨论。

情形1： $\left|V\left(C_1\right)\right|\ge 3$ 且 $\left|V\left(C_2\right)\right|\ge 4$ 。

情形1.1：如果 ${\mathcal{l}}_{C_1}={\mathcal{l}}_{C_2}=0$ ，选择两个相邻顶点u，v并且 $\left\{u,v\right\}\in V\left(C_1\right)$ 不同于顶点s及其邻点 $w\in V\left(C_2\right)$ 。显然， $\left\{u,v,w\right\}$ 及G的所有悬挂顶点构成G的一个零强迫集，那么 $F\left(G\right)\le \left|\left\{u,v,w\right\}\right|+\mathcal{l}=\mathcal{l}+3$ 。选择四个顶点 $x,y,m,n$ ，其中 $x,y\in V\left(C_1\right)$ ， $m,n\in V\left(C_2\right)$ ， $d\left(x,y\right)=dp\left(C_1\right)$ ， $d\left(m,n\right)=dp\left(C_2\right)$ 并且 $\left|d\left(x,s\right)-d\left(y,s\right)\right|\le 1$ ， $\left|d\left(m,t\right)-d\left(n,t\right)\right|\le 1$ ，那么G的所有悬挂顶点及 $\left\{x,y,m,n\right\}$ 构成G的一个一般位置集，可得 $gp\left(G\right)\ge \mathcal{l}+\left|\left\{x,y,m,n\right\}\right|=\mathcal{l}+4>\mathcal{l}+3\ge F\left(G\right)$ 。

情形1.2：如果 ${\mathcal{l}}_{C_1}=0$ ， ${\mathcal{l}}_{C_2}\ne 0$ (或者 ${\mathcal{l}}_{C_2}=0$ ， ${\mathcal{l}}_{C_1}\ne 0$ )，选择一个顶点 $w\in V\left(C_2\right)$ 是C₂中的一个分叉顶点的邻点， $u\in V\left(C_1\right)$ 是C₁中s的一个邻点，那么所有悬挂顶点及 $\left\{u,w\right\}$ 构成G的一个零强迫集，可得 $F\left(G\right)\le \mathcal{l}+\left|\left\{u,w\right\}\right|=\mathcal{l}+2$ 。选择两个顶点 $x,y\in V\left(C_1\right)$ ， $d\left(x,y\right)=dp\left(C_1\right)$ 并且 $\left|d\left(x,s\right)-d\left(y,s\right)\right|\le 1$ ，那么 $\left\{x,y\right\}$ 和所有悬挂顶点构成G的一个一般位置集，可得 $gp\left(G\right)\ge \mathcal{l}+\left|\left\{x,y\right\}\right|=\mathcal{l}+2$ 。

情形1.3：如果 ${\mathcal{l}}_{C_1}\ne 0$ 并且 ${\mathcal{l}}_{C_2}\ne 0$ ，选取C₁中的一个分叉顶点的邻点 $u\in V\left(C_1\right)\backslash \left\{s\right\}$ 和s的一个邻点 $w\in V\left(C_2\right)$ ，那么 $\left\{u,w\right\}$ 及除C₂中一个悬挂顶点之外所有悬挂顶点构成G的一个零强迫集，得到 $F\left(G\right)\le \mathcal{l}-1+\left|\left\{u,w\right\}\right|=\mathcal{l}+1$ 。而所有的悬挂顶点构成G的一个一般位置集，得到 $gp\left(G\right)\ge \mathcal{l}$ 。但无法直接得到不等式(1)。

情形2： $\left|V\left(C_1\right)\right|=\left|V\left(C_2\right)\right|=3$ ， $V\left(C_1\right)\cap V\left(C_2\right)=\left\{s\right\}$ 。

设 $\left\{u,v\right\}\in V\left(C_1\right)$ 和 $w,x\in V\left(C_2\right)$ 分别是顶点s在C₁和C₂中的邻点，分以下几种情况讨论。

情形2.1：如果 ${\mathcal{l}}_{C_1}={\mathcal{l}}_{C_2}=0$ ，所有悬挂顶点和 $\left\{u,v,w\right\}$ 构成G的一个零强迫集，而 $\left\{u,v,w,x\right\}$ 和所有悬挂顶点构成G的一个一般位置集，可得 $F\left(G\right)\le \mathcal{l}+3<\mathcal{l}+4\le gp\left(G\right)$ 。

情形2.2：如果 ${\mathcal{l}}_{C_1}=0$ ， ${\mathcal{l}}_{C_2}\ne 0$ (或者 ${\mathcal{l}}_{C_2}=0$ ， ${\mathcal{l}}_{C_1}\ne 0$ )， $\left\{u,v\right\}$ 和所有悬挂顶点构成G的一个零强迫集，同时也构成G的一个一般位置集，那么我们可得 $F\left(G\right)\le \mathcal{l}+2<\mathcal{l}+3\le gp\left(G\right)$ 。

情形2.3：如果 ${\mathcal{l}}_{C_1}\ne 0$ 并且 ${\mathcal{l}}_{C_2}\ne 0$ ，我们考虑 $\left\{u,v,w,x\right\}$ 中的分叉顶点数。当C₁和C₂中都恰好有一个分叉顶点时，不失一般性，假设u，w是分叉顶点，那么 和所有悬挂顶点构成G的一个零强迫集，而 $\left\{v,x\right\}$ 和所有悬挂顶点形成G的一个一般位置集，可得 $F\left(G\right)\le \mathcal{l}+1<\mathcal{l}+2\le gp\left(G\right)$ (如图6所示)；当 $\left\{u,v,w,x\right\}$ 中只有一个不是分叉顶点时，不失一般性，我们设x不是分叉顶点，那么x及G的所有悬挂顶点构成G的一个一般位置集，而所有悬挂顶点构成G的一个零强迫集，那么 $F\left(G\right)\le \mathcal{l}<l+1\le gp\left(G\right)$ (如图7所示)；当 $\left\{u,v,w,x\right\}$ 都是分叉顶点时，所有悬挂顶点构成G的一个一般位置集，而除一个外所有悬挂顶点构成G的一个零强迫集，可得 $F\left(G\right)\le \mathcal{l}-1<\mathcal{l}\le gp\left(G\right)$ (如图8所示)。

图6. $u,w$ 是分叉顶点

图7. x不是分叉顶点

图8. $u,v,w,x$ 是分叉顶点

综上所述， $G\in \mathcal{A}$ 包含结构 ${\alpha }_2$ ，并且 $G\notin \mathcal{B}$ 时， $gp\left(G\right)\ge F\left(G\right)$ 。证明完成。

引理6：若 $G\in \mathcal{A}$ 包含结构 ${\alpha }_3$ ，并且图G中两个圈恰好有一条公共边，则 $gp\left(G\right)\ge F\left(G\right)$ 。

证明：设 $G\in \mathcal{A}$ 包含结构 ${\alpha }_3$ ，并且图G中两个圈恰好有一条公共边，不失一般性，假设P₃长为 ，也就是说， $\left|V\left(P\right)\right|=\left|\left\{s,t\right\}\right|=2$ 。我们分一下两种情况讨论，并根据圈上分叉顶点的存在性分为几种子情况。

情形1： $\left|V\left(P_1\right)\right|\ge 3$ ， $\left|V\left(P_2\right)\right|\ge 4$ ，其中 $V\left(P_1\right)\cap V\left(P_2\right)\cap V\left(P_3\right)=\left\{s,t\right\}$ 。

情形1.1：如果 ${\mathcal{l}}_{P_1}={\mathcal{l}}_{P_2}=0$ ，我们考虑 ${\mathcal{l}}_s$ 和 ${\mathcal{l}}_t$ 的值。设 $u\in V\left(P_1\right)$ ， $v\in V\left(P_2\right)$ 分别是s在P₁和P₂上的邻点，设 $x\in V\left(P_1\right)$ ， $y\in V\left(P_2\right)$ 分别是t在P₁和P₂上的邻点(u，x可能为同一个顶点)。当 ${\mathcal{l}}_s={\mathcal{l}}_t=0$ 时， $\left\{u,s\right\}$ 是G的一个零强迫集， $\left\{s,x,y\right\}$ 是G的一个一般位置集，则可得 $F\left(G\right)\le 2<3\le gp\left(G\right)$ ；当 ${\mathcal{l}}_s=0$ ， ${\mathcal{l}}_t\ne 0$ (或者 ${\mathcal{l}}_s\ne 0$ ， ${\mathcal{l}}_t=0$ )时，根据引理4.1.4， $\left\{u,v,s\right\}$ 和除一个外G的所有悬挂顶点是G的一个零强迫集， $\left\{x,y\right\}$ 和所有悬挂顶点构成G的一个一般位置集，可得 $F\left(G\right)\le \mathcal{l}+2\le gp\left(G\right)$ ；当 ${\mathcal{l}}_s\ne 0$ 并且 ${\mathcal{l}}_t\ne 0$ 时，u和所有悬挂顶点是G的一个零强迫集，x和所有悬挂顶点构成G的一个一般位置集，则可得 $F\left(G\right)\le \mathcal{l}+1\le gp\left(G\right)$ 。

情形1.2：如果 ${\mathcal{l}}_{P_1}=0$ ， ${\mathcal{l}}_{P_2}\ne 0$ (或者 ${\mathcal{l}}_{P_2}=0$ ， ${\mathcal{l}}_{P_1}\ne 0$ )，选取顶点 $u\in V\left(P_1\right)$ 是s的一个邻点(如果有必要，也可以假设为顶点t的邻点)，则 $\left\{u,s\right\}$ 和除一个外所有悬挂顶点是G的一个零强迫集，那么 $F\left(G\right)\le \mathcal{l}+1$ 。任意 $x\in V\left(P_1\right)\backslash \left\{s,t\right\}$ 和所有悬挂顶点构成G的一个一般位置集，则可得 $gp\left(G\right)\ge \mathcal{l}+1\ge F\left(G\right)$ 。

情形1.3：如果 ${\mathcal{l}}_{P_1}\ne 0$ 并且 ${\mathcal{l}}_{P_2}\ne 0$ ，选择P₁中任意分叉顶点的一个邻点 $u\in V\left(P_1\right)$ ，u和除一个外所有悬挂顶点是G的一个零强迫集，那么 $F\left(G\right)\le \mathcal{l}$ 。而所有悬挂顶点构成G的一个一般位置集，可得 $gp\left(G\right)\ge \mathcal{l}$ 。

情形2： $\left|V\left(P_1\right)\right|=\left|V\left(P_2\right)\right|=3$ 并且 $V\left(P_1\right)\cap V\left(P_2\right)=\left\{s,t\right\}$ 。

设 $u\in V\left(P_1\right)\backslash \left\{s\right\}$ ， $v\in V\left(P_2\right)\backslash \left\{s\right\}$ ，分以下几种情况讨论。

情形2.1：如果 ${\mathcal{l}}_{P_1}={\mathcal{l}}_{P_2}=0$ ， $\left\{s,u\right\}$ 和所有悬挂顶点是G的一个零强迫集，而 $\left\{u,v\right\}$ 和所有悬挂顶点构成G的一个一般位置集，那么 $F\left(G\right)\le \mathcal{l}+2\le gp\left(G\right)$ 。

情形2.2：如果 ${\mathcal{l}}_{P_1}=0$ ， ${\mathcal{l}}_{P_2}\ne 0$ (或者 ${\mathcal{l}}_{P_2}=0$ ， ${\mathcal{l}}_{P_1}\ne 0$ )，s和所有悬挂顶点是G的一个零强迫集，所有悬挂顶点和u构成G的一个一般位置集，那么 $F\left(G\right)\le \mathcal{l}+1\le gp\left(G\right)$ 。

情形2.3：如果 ${\mathcal{l}}_{P_1}\ne 0$ 并且 ${\mathcal{l}}_{P_2}\ne 0$ ，s和除一个外所有悬挂顶点是G的一个零强迫集，而所有悬挂顶点构成G的一个一般位置集，那么 $F\left(G\right)\le \mathcal{l}\le gp\left(G\right)$ 。

因此，当 $G\in \mathcal{A}$ 包含结构 ${\alpha }_3$ ，并且图G中两个圈恰好有一条公共边时， $gp\left(G\right)\ge F\left(G\right)$ 。证明完成。

引理7：若 $G\in \mathcal{A}$ 包含结构 ${\alpha }_3$ ，并且 $G\notin \mathcal{B}$ ，则 $gp\left(G\right)\ge F\left(G\right)$ 。

证明：设 $G\in \mathcal{A}$ 包含结构 ${\alpha }_3$ ，由引理6，我们只需考虑图G中两个圈至少有两条公共边的情况，也就是 $d\left(s,t\right)\ge 2$ 。

情形1： $\left|V\left(P_1\right)\right|\ge 3,\left|V\left(P_2\right)\right|\ge 3$ 且 $V\left(P_3\right)\ge 4$ 。

情形1.1：如果 ${\mathcal{l}}_{P_1}={\mathcal{l}}_{P_2}={\mathcal{l}}_{P_3}=0$ ，设 $u\in V\left(P_1\right),v\in V\left(P_2\right)$ 和 $w\in V\left(P_3\right)$ 分别是t在 $P_1,P_2,P_3$ 上的邻点。我们现在讨论 ${\mathcal{l}}_s$ 和 ${\mathcal{l}}_t$ 的值。当 ${\mathcal{l}}_s={\mathcal{l}}_t=0$ 时， $\left\{u,v,t\right\}$ 是G的一个零强迫集并且 $F\left(G\right)\le 3$ ， $\left\{u,v,w\right\}$ 是G的一个一般位置集并且 $gp\left(G\right)\ge 3\ge F\left(G\right)$ (如图9所示)；当 ${\mathcal{l}}_s=0$ ， ${\mathcal{l}}_t\ne 0$ (或者 ${\mathcal{l}}_s\ne 0$ ， ${\mathcal{l}}_t=0$ )时， $\left\{u,v\right\}$ 和所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+2$ ， $\left\{u,v,w\right\}$ 和所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}+3>\mathcal{l}+2\ge F\left(G\right)$ (如图10所示)；当 ${\mathcal{l}}_s\ne 0$ 并且 ${\mathcal{l}}_t\ne 0$ 时，所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}$ ，而 $\left\{u,v\right\}$ 和除一个外所有悬挂顶点构成G的一个零强迫集，并且 $F\left(G\right)\le \mathcal{l}+1$ (如图11所示)。不能得到不等式(1)。特别地，如果 ${\mathcal{l}}_s\le 2$ ， ${\mathcal{l}}_t\ge 1$ (或者反过来)，那么 $\left\{u,v,w\right\}$ 和 $T\left(t\right)$ 的所有悬挂顶点构成G的一个一般位置集，则可得 $F\left(G\right)\le \mathcal{l}+1=3+\mathcal{l}-2\le gp\left(G\right)$ (如图12所示)，即，当 ${\mathcal{l}}_s,{\mathcal{l}}_t\ge 3$ 时，不能得到不等式(1)。

图9. ${\mathcal{l}}_s={\mathcal{l}}_t=0$

图10. ${\mathcal{l}}_s=0$ ， ${\mathcal{l}}_t\ne 0$

图11. ${\mathcal{l}}_s\ne 0$ 并且 ${\mathcal{l}}_t\ne 0$

图12. ${\mathcal{l}}_s\le 2$ ， ${\mathcal{l}}_t\ge 1$

情形1.2：如果 ${\mathcal{l}}_{P_i}={\mathcal{l}}_{P_j}=0$ ， ${\mathcal{l}}_{P_k}\ne 0$ ，其中 $i,j,k=1,2,3$ 并且 $i\ne j\ne k$ ，不失一般性，假设 ${\mathcal{l}}_{P_1}={\mathcal{l}}_{P_2}=0$ 并且 ${\mathcal{l}}_{P_3}\ne 0$ 。设 $\left\{u,v\right\}\in V\left(P_3\right)\backslash \left\{s,t\right\}$ 是P₃中两个相邻顶点， $w\in V\left(P_2\right)$ 是s在P₂中的邻点，那么 $\left\{u,v,w\right\}$ 和除一个外所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+2$ ，所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}$ ，不能得到不等式(1)。

情形1.3：如果 ${\mathcal{l}}_{P_i}=0$ ， ${\mathcal{l}}_{P_j}\ne 0$ ， ${\mathcal{l}}_{P_k}\ne 0$ ，不失一般性，假设 ${\mathcal{l}}_{P_1}=0$ ， ${\mathcal{l}}_{P_2}\ne 0$ 并且 ${\mathcal{l}}_{P_3}\ne 0$ 。设 $u\in V\left(P_1\right)$ 是s的邻点， $v\in V\left(P_2\right)$ 是P₂上的一个分叉顶点的邻点。那么 $\left\{u,v\right\}$ 和除一个外所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+1$ ，而所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}$ ，也不能得到不等式(1)。

情形1.4：如果 ${\mathcal{l}}_{P_i}\ne 0$ ， ${\mathcal{l}}_{P_j}\ne 0$ ， ${\mathcal{l}}_{P_k}\ne 0$ ，设 $u\in V\left(P_3\right)\backslash \left\{s,t\right\}$ 是一个分叉顶点， $v\in V\left(P_1\right)\backslash \left\{s,t\right\}$ 是P₃中u的一个邻点， $w\in V\left(P_2\right)$ 是P₂中s的一个邻点，那么 $\left\{v,w\right\}$ 和除一个外所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+1$ ，而所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}$ ，同样不能得到不等式(1)。

情形2： $\left|V\left(P_1\right)\right|=\left|V\left(P_2\right)\right|=\left|V\left(P_3\right)\right|=3$ 。

设 $u,v,w$ 分别是s在 $P_1,P_2,P_3$ 上的邻点，其中 $u\in V\left(P_1\right)$ ， $v\in V\left(P_2\right)$ 并且 $w\in V\left(P_3\right)$ ，分下面几种子情况讨论。

情形2.1：如果 ${\mathcal{l}}_{P_1}={\mathcal{l}}_{P_2}={\mathcal{l}}_{P_3}=0$ ，我们讨论 ${\mathcal{l}}_s$ 和 ${\mathcal{l}}_t$ 的值。当 ${\mathcal{l}}_s={\mathcal{l}}_t=0$ 时， $\left\{u,v,s\right\}$ 是G的一个零强迫集并且 $F\left(G\right)\le 3$ ， $\left\{u,v,w\right\}$ 是G的一个一般位置集并且 $gp\left(G\right)\ge 3\ge F\left(G\right)$ (如图13所示)；当 ${\mathcal{l}}_s=0$ ， ${\mathcal{l}}_t\ne 0$ (或者 ${\mathcal{l}}_s\ne 0$ ， ${\mathcal{l}}_t=0$ )时， $\left\{u,v\right\}$ 和所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+2$ ， $\left\{u,v,w\right\}$ 和所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}+3>\mathcal{l}+2\ge F\left(G\right)$ (如图14所示)；当 ${\mathcal{l}}_s\ne 0$ 并且 ${\mathcal{l}}_t\ne 0$ 时，所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}$ ， $\left\{u,v\right\}$ 和除一个外所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+1$ (如图15所示)，不能得到不等式(1)。特别地，如果 ${\mathcal{l}}_s\le 2$ ， ${\mathcal{l}}_t\ge 1$ (或者 ${\mathcal{l}}_t\le 2$ ， ${\mathcal{l}}_s\ge 1$ )，那么 $\left\{u,v\right\}$ 和除一个外所有悬挂顶点构成G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+1$ ，而 $\left\{u,v,w\right\}$ 和 $T\left(t\right)$ 的所有悬挂顶点构成G的一个一般位置集，可得 $gp\left(G\right)\ge {\mathcal{l}}_t+3=\mathcal{l}-{\mathcal{l}}_s+3\ge \mathcal{l}+1\ge F\left(G\right)$ (如图16所示)，即，当 ${\mathcal{l}}_s,{\mathcal{l}}_t\ge 3$ 时，不能得到不等式(1)。

图13. ${\mathcal{l}}_s={\mathcal{l}}_t=0$

图14. ${\mathcal{l}}_s=0$ ， ${\mathcal{l}}_t\ne 0$

图15. ${\mathcal{l}}_s\ne 0$ 并且 ${\mathcal{l}}_t\ne 0$

图16. ${\mathcal{l}}_s\le 2$ ， ${\mathcal{l}}_t\ge 1$

情形2.2：如果 ${\mathcal{l}}_{P_i}={\mathcal{l}}_{P_j}=0$ ， ${\mathcal{l}}_{P_k}\ne 0$ ，其中 $i,j,k=1,2,3$ 并且 $i\ne j\ne k$ ，不失一般性，我们假设 ${\mathcal{l}}_{P_1}={\mathcal{l}}_{P_2}=0$ 并且 ${\mathcal{l}}_{P_3}\ne 0$ 。当 ${\mathcal{l}}_s={\mathcal{l}}_t=0$ 时， $\left\{u,s\right\}$ 和所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+2$ ，而 $\left\{u,v\right\}$ 和所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}+2\ge F\left(G\right)$ ；当 ${\mathcal{l}}_s=0$ ， ${\mathcal{l}}_t\ne 0$ (或者 ${\mathcal{l}}_s\ne 0$ ， ${\mathcal{l}}_t=0$ )时，u和所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+1$ ， $\left\{u,v\right\}$ 和所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}+2$ ；当 ${\mathcal{l}}_s\ne 0$ 并且 ${\mathcal{l}}_t\ne 0$ 时，所有悬挂顶点构成G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}$ ，u和所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+1\le gp\left(G\right)$ 。

情形2.3：如果 ${\mathcal{l}}_{P_i}=0$ ， ${\mathcal{l}}_{P_j}\ne 0$ ， ${\mathcal{l}}_{P_k}\ne 0$ ，不失一般性，假设 ${\mathcal{l}}_{P_1}=0$ ， ${\mathcal{l}}_{P_2}\ne 0$ 并且 ${\mathcal{l}}_{P_3}\ne 0$ 。当 ${\mathcal{l}}_s={\mathcal{l}}_t=0$ 时，s和所有悬挂顶点是G的一个零强迫集并且 $F\left(G\right)\le \mathcal{l}+1$ ，而u和所有悬挂顶点是G的一个一般位置集并且 $gp\left(G\right)\ge \mathcal{l}+1$ ；当 ${\mathcal{l}}_s=0,{\mathcal{l}}_t\ne 0$ (或者反过来)时，所有悬挂顶点是G的一个零强迫集同时构成G的一个一般位置集，那么 $F\left(G\right)\le \mathcal{l}\le gp\left(G\right)$ ；当 ${\mathcal{l}}_s\ne 0$ 并且 ${\mathcal{l}}_t\ne 0$ 时，s和除一个外G的所有悬挂顶点是G的一个一般位置集，并且所有悬挂顶点是G的一个零强迫集，则可得 $F\left(G\right)\le \mathcal{l}\le gp\left(G\right)$ 。

情形2.4：如果 ${\mathcal{l}}_{P_i}\ne 0$ ， ${\mathcal{l}}_{P_j}\ne 0$ ， ${\mathcal{l}}_{P_k}\ne 0$ ，当 ${\mathcal{l}}_s={\mathcal{l}}_t=0$ 时，s和除一个外所有悬挂顶点是G的一个零强迫集并且所有悬挂顶点是G的一个一般位置集，那么 $F\left(G\right)\le \mathcal{l}\le gp\left(G\right)$ 。

证明完成。

结合引理4~引理7，若 $G\in \mathcal{B}$ ，无法确定图G中零强迫数与一般位置数的关系，但 $G\in \mathcal{A}\backslash \mathcal{B}$ ，有 $gp\left(G\right)\ge F\left(G\right)$ ，即定理3成立。

3. 总结与展望

本文通过分析双圈图的三种结构得到零强迫数与一般位置数的关系，刻画了使得 $gp\left(G\right)\ge F\left(G\right)$ 成立的双圈图的结构。但是当 $G\in \mathcal{B}$ 时无法确定图G的零强迫数与一般位置数的关系，我们猜想，当 $G\in \mathcal{B}$ 时存在某些特殊结构，可以使F(G)减小或者使gp(G)增大从而得到 $F\left(G\right)\le gp\left(G\right)$ ，因此这个问题仍是我们需要研究的。

文章引用

荆 瑜. 双圈图的零强迫数与一般位置数
Zero Forcing Number and General Position Number in Bicyclic Graphs[J]. 应用数学进展, 2023, 12(04): 1897-1907. https://doi.org/10.12677/AAM.2023.124196

参考文献