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

doi:10.15960/j.cnki.issn.1007-6093.2024.01.013

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

• • 上一篇

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

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

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 SU¹, Xiaohui LI¹, Yan LIU¹^,*()

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

摘要/Abstract

摘要：

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

中图分类号:

O157.5

苏雪丽, 李晓辉, 刘岩. 二维四角网格图的反馈数上界的改进[J]. 运筹学学报（中英文）, 2024, 28(1): 153-158.

Xueli SU, Xiaohui LI, Yan LIU. Improved upper bound of feedback number for 2-dimensional meshes[J]. Operations Research Transactions, 2024, 28(1): 153-158.

图/表 3

参考文献 8

1	Wilfong G, Winkler P. Ring routing and wavelength translation [C]// Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998: 333-341.
2	Luccio F L , Sibeyn J F . Feedback vertex sets in mash-based networks[J]. Theoretical Computer Science, 2007, 383, 86- 101. doi: 10.1016/j.tcs.2007.03.051
3	Xu X R , Hang Y Z , Zhang S J , et al. Feedback numbers of generalized Kautz digraphs $GK(3, n)$[J]. Computer Science, 2016, 43 (5): 13- 21.
4	Garey M R , Johnson D S . Computer and Intractability[M].
5	Peleg D. Local majority voting, small coalitions and controlling monopolies in graphs: A review [C]// Colloquium on Structural Information and Communication Complexity, Ottawa: Carleton University Press, 1996: 152-169.
6	Peleg D. Size bounds for dynamic monopolies [C]// Colloquium on Structural Information and Communication Complexity, Ottawa: Carleton University Press, 1997: 165-175.
7	Luccio F L . Almost exact minimum feedback vertex set in meshes and butterflies[J]. Information Processing Letters, 1998, 66 (2): 59- 64. doi: 10.1016/S0020-0190(98)00039-8
8	Caragiannis I , Kaklamanis C , Kanellopoulos P . New bounds on the size of the minimum feedback vertex set in meshes and butterflies[J]. Information Processing Letters, 2002, 83 (5): 275- 280. doi: 10.1016/S0020-0190(02)00266-1

[1]	邢抱花, 孙旻昊, 余桂东. 给定独立数的树的倒数度距离[J]. 运筹学学报（中英文）, 2024, 28(2): 143-150.
[2]	余桂东, 刘珍珍, 王礼想, 李青. 可迹图的一些新充分条件[J]. 运筹学学报（中英文）, 2024, 28(1): 131-140.
[3]	刘乐乐, 宁博. 谱图理论中的未解决问题[J]. 运筹学学报, 2023, 27(4): 33-60.
[4]	郝建修. 关于网络的控制数的几点注记[J]. 运筹学学报, 2023, 27(3): 185-190.
[5]	张杰, 姬燕. 单圈图的Steiner Wiener指数的极值问题[J]. 运筹学学报, 2023, 27(3): 178-184.
[6]	袁玲, 王文环. 不含偶圈(n, m)-图匹配多项式的最大根[J]. 运筹学学报, 2023, 27(3): 150-158.
[7]	崔福祥, 杨超, 叶宏波, 姚兵. 图的邻点全和可区别全染色[J]. 运筹学学报, 2023, 27(1): 149-158.
[8]	王蝶, 康丽英. 一般超图的张量谱性质[J]. 运筹学学报, 2023, 27(1): 138-148.
[9]	李春梅, 王治文. Δ(G)=5的2-连通外平面图的邻点可区别全染色[J]. 运筹学学报, 2021, 25(4): 120-126.
[10]	董艳侠, 薛涛, 张广. 广义de Bruijn有向图的k-元控制集[J]. 运筹学学报, 2021, 25(2): 127-134.
[11]	刘瑶. 带松弛条件的图的强边着色[J]. 运筹学学报, 2021, 25(2): 115-126.
[12]	林晓霞. 关于拟k-连通图的一个注释[J]. 运筹学学报, 2021, 25(1): 137-140.
[13]	陈敏, 杨建民, 张豪, 王依婷. 外平面图的弱完备染色[J]. 运筹学学报, 2021, 25(1): 132-136.
[14]	赵静, 单而芳, 赵加贵. 最大边连通和super-边连通超图的充分条件[J]. 运筹学学报, 2021, 25(1): 123-131.
[15]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.

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

Improved upper bound of feedback number for 2-dimensional meshes

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 8

相关文章 15

编辑推荐

Metrics

本文评价