华东师范大学学报(自然科学版)

作者：叶宏波, 杨超, 崔福祥

关键词：图,消圈数,联图,

基金：国家自然科学基金(61672001, 61662066, 62072296)

设图 $G = (V, E)$ , 对于 $V$ 中任何一个点集 $S$ , 若 $G - S$ 是一个无圈图, 则称 $S$ 是图 $G$ 的一个消圈集, 且称min{|S||S是图G的消圈集}为图 $G$ 的消圈数, 记为 $\phi \left( G \right)$ . 本文考虑联图的消圈问题, 得到了几类联图消圈数的精确值. 设 ${G_m}$ 和 ${G_n}$ 分别表示阶数为m和n的简单连通图, 则联图 ${G_m} \vee {G_n}$ 的消圈数满足: $\min \{ m,n\} \leqslant \phi ({G_m} \vee {G_n}) \leqslant \min \{ m + \phi ({G_n}),n + \phi ({G_m})\}$ . 本文中几类联图的消圈数证实了上述不等式的上界是紧的. 特别地, 当 ${G_m}$ 和 ${G_n}$ 都为树时，可由不等式直接得到 $\phi ({G_m} \vee {G_n})$ 的精确值.

来源：2022年第1期

《华东师范大学学报(自然科学版)》期刊编辑部

查看华东师范大学学报(自然科学版)杂志2022年第1期