单圈图的零强迫和全强迫

展开
  • 1. 山东理工大学数学与统计学院, 山东淄博 255000
计省进, E-mail: jishengjin@sdut.edu.cn

收稿日期: 2021-07-20

  网络出版日期: 2025-03-08

基金资助

山东省自然科学基金(ZR2019MA012)

版权

运筹学学报编辑部, 2025, 版权所有,未经授权,不得转载。

Total forcing and zero forcing of unicyclic graphs

Expand
  • 1. School of Mathematics and Statistics, Shandong University of Technology, Zibo 255000, Shandong, China

Received date: 2021-07-20

  Online published: 2025-03-08

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

摘要

$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$

本文引用格式

李宝欣, 计省进 . 单圈图的零强迫和全强迫[J]. 运筹学学报, 2025 , 29(1) : 198 -206 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.016

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$.

参考文献

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.
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.
7 Kalinowski T , Kamcev N , Sudakov B . The zero forcing number of graphs[J]. SIAM Journal on Discrete Mathematics, 2019, 33 (1): 95- 115.
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.
9 Davila R , Henning M A . On the total forcing number of a graph[J]. Discrete Applied Mathematics, 2019, 257, 115- 127.
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.
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.
13 Burgarth D , Giovannetti V , Hogben L , et al. Logic circuits from zero forcing[J]. Natural Computing, 2015, 14 (3): 485- 490.
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.
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.
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.
20 Gentner M , Rautenbanch D . Some bounds on the zero forcing number of a graph[J]. Discrete Applied Mathematics, 2018, 236, 203- 213.
21 Davila R , Henning M A . The forcing number of graphs with a given girth[J]. Quaestiones Mathematicae, 2018, 41, 189- 204.
文章导航

/