报 告 人：徐守军 教授 兰州大学
报告题目：Characterizations on graphs which achieve some upper bounds for their zero forcing number
报告时间：2022年4月1日（周五）上午09:10
报告地点：腾讯会议（会议ID：320-563-107会议密码：202241）
主办单位：数学与统计学院、科学技术研究院
报告人简介：
徐守军,兰州大学教授、博士生导师，数学与统计学院副院长。现任中国运筹学会图论组合学分会第四届理事会青年理事， 中国工业与应用数学学会图论组合及应用专业委员会委员。2007年获得兰州大学博士学位， 2008-2010年，在中科院数学与系统科学研究院从事运筹学方向博士后工作；多次出访美国加州大学戴维斯分校计算机系和香港教育学院。 主要研究领域为图论及组合最优化、计算机算法及离散数学等。在SIAM J Discrete Math， Discrete Appl. Math, J. Combin. Optim.，Int. J. Quantum Chem, MATCH, Australas. J. Combin.等国际期刊上发表论文三十余篇。 2012年，获得甘肃省自然科学奖三等奖； 2013年，获得甘肃省高等学校青年教师成才奖；2015年，获兰州大学隆基教学骨干奖； 2019年, 获全纳教育人物贡献奖。目前主持国家基金面上项目一项，主持完成了国家基金青年基金一项及专项基金一项和博士后基金一等资助一项。
报告摘要：
Let $G$ be a connected graph of order $n$ with vertex set $V(G)$. A set $S\subseteq V(G)$ is a zero forcing set of $G$ if initially the vertices in $S$ are colored black and the remaining vertices are colored white, and then forcing a white vertex to black if it is the only white neighbor of some black vertex, applying this step iteratively until all vertices of $G$ are black. The zero forcing number $Z(G)$ of $G$ is defined as the minimum cardinality of a zero forcing set of $G$. In a recent work [Theory Appl. Graphs 2(2) (2015) Article 2] Caro and Pepper used a greedy algorithm to prove that $Z(G)\leq \frac{(\Delta-2)n-(\Delta-\delta)+2}{\Delta-1}$, where $\delta$, $\Delta\geq 2$ are minimum degree, maximum degree of $G$, respectively. If $G$ is regular, i.e., $\delta=\Delta$, this upper bound was characterized independently by Gentner et al. and Lu et al. in 2016. First, we completely characterize general graphs attained the upper bound, solving the question proposed by Lu et al.. On the other hand, $Z(G)\leq n-g+2$, where $g$ is the girth of $G$. Second, we slightly improved the bound and characterize connected graphs attained the improved bound.