二维四角网格图的反馈数上界的改进  

Improved upper bound of feedback number for 2-dimensional meshes

作　　者：苏雪丽 李晓辉 刘岩[1] SU Xueli;LI Xiaohui;LIU Yan(Schoolof Mathematical Science,South China Normal University,Guangzhou 510631,Guangdong,China)

机构地区：[1]华南师范大学数学科学学院,广东广州510631

出　　处：《运筹学学报（中英文）》2024年第1期153-158,共6页Operations Research Transactions

基　　金：广州市科技计划项目(No.202002030183);广东省自然科学基金(No.2021A1515012045);青海省自然科学基金(No.2020-ZJ-924)。

摘　　要：设G=(V,E)是简单图,子集F?V。若由点集V-F导出的子图不含圈,则称子集F是图G的反馈集。称反馈集的点数的最小值是图G的反馈数,用f(G)表示,即,f(G)=min{|F|:F是图G的反馈集}。Caragiannis等人给出了二维四角网格图反馈数的上界,本文改进了其上界。Let G=(V,E)be a simple graph and F be a subset of V.If the subgraph induced by the subset V-F does not contain cycles,then F is called a feedback set of G.The smallest value of the numbers of vertices in feedback sets is called the feedback number of G,denoted by f(G),that is,f(G)=min{|F|:F is a feedback set of G}.Caragiannis et al.obtained the upper bounds of the feedback number of 2-dimensional meshes.In this paper,we improve the upper bounds.

关 键 词：二维四角网格图 反馈点集 反馈数 无圈子图 

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