单圈图的零强迫和全强迫

doi:10.15960/j.cnki.issn.1007-6093.2025.01.016

摘要/Abstract

摘要：

设 $S\subseteq V$ 是一个初始着色顶点子集, 它的所有顶点都着黑色, $S$ 中的每个顶点称为 $S$ -着色, $G$ 中所有其他未着色的顶点称为 $S$ -未着色。若一个着黑色的顶点 $v$ 恰好只有一个未着色的邻点 $u$ , 则 $v$ 强迫顶点 $u$ 着黑色, 这样的过程称为强迫过程。如果从一个初始顶点集 $S$ 出发, 逐步运用强迫过程直到 $G$ 中所有的顶点都变成黑色, 则称这个初始集 $S$ 为 $G$ 的零强迫集(强迫集)。 $G$ 的零强迫集的最小基数用 $F (G)$ 表示, 称为 $G$ 的零强迫数。如果 $S$ 在 $G$ 中的导出子图 $G[S]$ 不包含孤立顶点, 则强迫集 $S$ 称为 $G$ 的全强迫集, 全强迫集的最小基数用 $F_t (G)$ 表示, 称为 $G$ 的全强迫数。注意到零强迫数和全强迫数有如下关系, $F (G)\leq F_t (G)\leq 2F (G)$ 。刻画满足 $F (G)＝F_t (G)$ 或者 $2F (G)＝F_t (G)$ 的图 $G$ 是有意义的。基于此, 本文在单圈图上刻画了满足 $F (G)＝F_t (G)$ 的所有图 $G$ 。此外, 本文研究了给定匹配数为 $k$ 的单圈图 $G$ 的零强迫数的上界, 即 $F (G)\leq n-k$ , 等号成立当且仅当 $G\cong C_4, A_0$ 。此外, 当 $G\not\cong C_4, A_0$ 时, 本文刻画了使得 $F (G)=n-k-1$ 的所有图 $G$ 。

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

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

中图分类号:

O157.5

李宝欣, 计省进. 单圈图的零强迫和全强迫[J]. 运筹学学报（中英文）, 2025, 29(1): 198-206.

Baoxin LI, Shengjin JI. Total forcing and zero forcing of unicyclic graphs[J]. Operations Research Transactions, 2025, 29(1): 198-206.

图/表 12

图1

$t=8$ 时, 零强迫和全强迫着色方式"

图1

图2

$t=r=8$ 时, 零强迫和全强迫着色方式"

图2

图3

图4

$m=5$ 时, 零强迫和全强迫着色方式(1)"

图4

图5

$m=5$ 时, 零强迫和全强迫着色方式(2)"

图5

图6

$m=3$ 时, 零强迫和全强迫着色方式"

图6

图7

$m=5$ 时, 零强迫和全强迫着色方式"

图7

图8

图9

图10

图11

图12

参考文献 21

1	AIM Minimum Rank-Special Graphs Work Group . Zero forcing sets and the minimum rank of graphs[J]. Linear Algebra and Its Applications, 2008, 428 (7): 1628- 1648. doi: 10.1016/j.laa.2007.10.009
2	Davila R. Bounding the forcing number of a graph [D]. Houston: Rice University, 2018.
3	Chekuri C, Korula N. A graph reduction step preserving element-connectivity and applications [M]//Automata, Languages and Programming, Berlin: Springer, 2009: 254-265.
4	Davila R, Kalinowski T, Stephen S. Proof of a conjecture of Davila and Kenter regarding a lower bound for the forcing number in terms of girth and minimum degree [EB/OL]. (2018-03-31)[2021-06-20]. arXiv: 1611.06557.
5	Edholm C , Hogben L , La Grange J , et al. Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph[J]. Linear Algebra & Its Applications, 2012, 436 (12): 4352- 4372.
6	Eroh L , Yi C K . A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[J]. Acta Mathematica Sinica, 2017, 33 (6): 731- 747. doi: 10.1007/s10114-017-4699-4
7	Kalinowski T , Kamcev N , Sudakov B . The zero forcing number of graphs[J]. SIAM Journal on Discrete Mathematics, 2019, 33 (1): 95- 115. doi: 10.1137/17M1133051
8	Davila R , Henning M A . Zero forcing in Claw-Free cubic graphs[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2020, 43, 673- 688. doi: 10.1007/s40840-018-00705-5
9	Davila R , Henning M A . On the total forcing number of a graph[J]. Discrete Applied Mathematics, 2019, 257, 115- 127. doi: 10.1016/j.dam.2018.09.001
10	Davila R , Henning M A . Total forcing sets and zero forcing sets in trees[J]. Discussiones Mathematicae Graph Theory, 2020, 40 (3): 733- 754. doi: 10.7151/dmgt.2136
11	Davila R, Henning M A. Total forcing and zero forcing in claw-free cubic graphs [EB/OL]. (2017-08-16)[2021-06-20]. arXiv: 1708.05041.
12	Burgarth D , Giovannetti V . Full control by locally induced relaxation[J]. Physical Review Letters, 2007, 99, 100501. doi: 10.1103/PhysRevLett.99.100501
13	Burgarth D , Giovannetti V , Hogben L , et al. Logic circuits from zero forcing[J]. Natural Computing, 2015, 14 (3): 485- 490. doi: 10.1007/s11047-014-9438-5
14	Barioli F , Barrett W , Fallat S , et al. Zero forcing parameters and minimum rank problems[J]. Linear Algebra and Its Applications, 2010, 433, 401- 411. doi: 10.1016/j.laa.2010.03.008
15	Hernandez G , Ranilla J , Ranilla-Cortina S . Zero forcing in triangulations[J]. Journal of Computational & Applied Mathematics, 2019, 354, 123- 130.
16	Benson K F, Ferrero D, Flagg M, et al. Power domination and zero forcing [EB/OL]. (2017-02-22)[2021-06-20]. arXiv: 1510.02421.
17	Chilakammari K , Dean N , Kang C X , et al. Iteration index of a zero forcing set in a graph[J]. Bulletin of the Institute of Combinatorics and Its Applications, 2012, 64, 57- 72.
18	Lu L , Wu B , Tang Z . Note: Proof of a conjecture on the zero forcing number of a graph[J]. Discrete Applied Mathematics, 2012, 160, 1994- 2005. doi: 10.1016/j.dam.2012.04.003
19	Gentner M , Penso L , Rautenbanch D , et al. Extremal values and bounds for the zero forcing number[J]. Discrete Applied Mathematics, 2016, 214, 196- 200. doi: 10.1016/j.dam.2016.06.004
20	Gentner M , Rautenbanch D . Some bounds on the zero forcing number of a graph[J]. Discrete Applied Mathematics, 2018, 236, 203- 213. doi: 10.1016/j.dam.2017.11.015
21	Davila R , Henning M A . The forcing number of graphs with a given girth[J]. Quaestiones Mathematicae, 2018, 41, 189- 204. doi: 10.2989/16073606.2017.1376230

编辑推荐 0

Metrics

阅读次数

全文

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	1	0	0	21

来源	本网站	其他网站

次数	7	15
比例	32%	68%

摘要

最新录用	在线预览	正式出版

0	0	78

来源	本网站	其他网站

次数	14	64
比例	18%	82%

[1]	张莹, 敬新奇, 王长军. 一个双拟阵下的最优定价存在性猜想[J]. 运筹学学报, 2023, 27(4): 166-174.
[2]	张杰, 姬燕. 单圈图的Steiner Wiener指数的极值问题[J]. 运筹学学报, 2023, 27(3): 178-184.
[3]	袁玲, 王文环. 不含偶圈(n, m)-图匹配多项式的最大根[J]. 运筹学学报, 2023, 27(3): 150-158.
[4]	张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.
[5]	余桂东, 阮征, 舒阿秀, 于涛. 单圈图的次大(拉普拉斯)分离度[J]. 运筹学学报, 2020, 24(4): 128-134.
[6]	林杨, 王应明. 不确定偏好序下的双边匹配博弈[J]. 运筹学学报, 2020, 24(1): 155-162.
[7]	李瞳, 王光辉, 周文玲. 图与超图中的彩色匹配综述[J]. 运筹学学报, 2019, 23(3): 77-90.
[8]	刘岩, 雷梦霞, 黄晓娴. 最大匹配的路变换图[J]. 运筹学学报, 2019, 23(2): 104-112.
[9]	李建荣. 中国高考招生匹配市场中的算法设计及公平激励机制[J]. 运筹学学报, 2019, 23(2): 75-85.
[10]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[11]	苟燕, 张新功. 具有时间与位置相关及维修限制的单机排序问题[J]. 运筹学学报, 2016, 20(3): 33-44.
[12]	黄晓娴, 刘岩, 吴博思. 关于分数k-因子临界图与分数k-可扩图的若干结果[J]. 运筹学学报, 2016, 20(1): 125-130.
[13]	简相国,袁西英,张曼. 单圈图和双圈图的最大无符号拉普拉斯分离度[J]. 运筹学学报, 2015, 19(2): 99-104.
[14]	梅若星, 王力工, 王陆华, 王展青. 单圈图H(p,tK_{1,m})的Laplacian谱刻画[J]. 运筹学学报, 2015, 19(1): 57-64.
[15]	李巧, 刘岩. 分数k-因子临界图的条件[J]. 运筹学学报, 2013, 17(4): 123-130.