单圈图的零强迫和全强迫  

Total forcing and zero forcing of unicyclic graphs

作　　者：李宝欣 计省进 LI Baoxin;JI Shengjin(School of Mathematics and Statistics,Shandong University of Technology,Zibo 255000,Shandong,China)

机构地区：[1]山东理工大学数学与统计学院,山东淄博255000

出　　处：《运筹学学报(中英文)》2025年第1期198-206,共9页Operations Research Transactions

基　　金：山东省自然科学基金(No.ZR2019MA012)。

摘　　要：设S■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)≤F_(t)(G)≤2F(G)。刻画满足F(G)=F_(t)(G)或者2F(G)=F_(t)(G)的图G是有意义的。基于此,本文在单圈图上刻画了满足F(G)=F_(t)(G)的所有图G。此外,本文研究了给定匹配数为k的单圈图G的零强迫数的上界,即F(G)≤n-k,等号成立当且仅当G≌C_(4),A_(0)。此外,当G■C_(4),A_(0)时,本文刻画了使得F(G)=n-k-1的所有图G。Let S■V be an initial vertex subset of coloring,and all vertices of S?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)≤F_(t)(G)≤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)≤n-k and equality holds if and only if G≌C_(4),A_(0).Moreover,we characterize all graphs such that their forcing number equal to n-k-1 if G■C_(4),A_(0).

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

分 类 号：O157.5[理学—数学]