English

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (1): 153-158.doi: 10.15960/j.cnki.issn.1007-6093.2024.01.013

•   • 上一篇    

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

苏雪丽1, 李晓辉1, 刘岩1,*()   

  1. 1. 华南师范大学数学科学学院, 广东广州 510631
  • 收稿日期:2020-09-16 出版日期:2024-03-15 发布日期:2024-03-15
  • 通讯作者: 刘岩 E-mail:liuyan@scnu.edu.cn
  • 基金资助:
    广州市科技计划项目(202002030183);广东省自然科学基金(2021A1515012045);青海省自然科学基金(2020-ZJ-924)

Improved upper bound of feedback number for 2-dimensional meshes

Xueli SU1, Xiaohui LI1, Yan LIU1,*()   

  1. 1. School of Mathematical Science, South China Normal University, Guangzhou 510631, Guangdong, China
  • Received:2020-09-16 Online:2024-03-15 Published:2024-03-15
  • Contact: Yan LIU E-mail:liuyan@scnu.edu.cn

RichHTML

1

PDF

59

摘要：

设$G=(V, E)$ 是简单图, 子集$F\subseteq V$。若由点集$V-F$ 导出的子图不含圈, 则称子集$F$ 是图$G$ 的反馈集。称反馈集的点数的最小值是图$G$ 的反馈数, 用$f(G)$ 表示，即，$f(G)=\min\{|F| : F$ 是图$G$ 的反馈集$\}$。Caragiannis等人给出了二维四角网格图反馈数的上界, 本文改进了其上界。

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

Abstract:

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.

Key words: 2-dimensional meshes, feedback vertex set, feedback number, acyclic subgraph

中图分类号: