华东师范大学学报（自然科学版） ›› 2022, Vol. 2022 ›› Issue (1): 17-21.doi: 10.3969/j.issn.1000-5641.2022.01.003

• 数学 • 上一篇    下一篇

联图的消圈数

叶宏波1(), 杨超1,2,*(), 崔福祥1   

  1. 1. 上海工程技术大学 数理与统计学院, 上海　201620
    2. 上海工程技术大学 智能计算与应用统计研究中心, 上海　201620
  • 收稿日期:2020-11-18 出版日期:2022-01-25 发布日期:2022-01-18
  • 通讯作者: 杨超 E-mail:yehongbo724@163.com;yangchaomath0524@163.com
  • 基金资助:
    国家自然科学基金(61672001, 61662066, 62072296)

The decycling number of join graphs

Hongbo YE1(), Chao YANG1,2,*(), Fuxiang CUI1   

  1. 1. School of Mathematics, Physics and Statistics, Shanghai University of Engineering Science, Shanghai　201620, China
    2. Center of Intelligent Computing and Applied Statistics, Shanghai University of Engineering Science, Shanghai　201620, China
  • Received:2020-11-18 Online:2022-01-25 Published:2022-01-18
  • Contact: Chao YANG E-mail:yehongbo724@163.com;yangchaomath0524@163.com

RichHTML

842

PDF

289

摘要：

设图 $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})$ 的精确值.

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

Abstract:

Let $G = (V, E)$ be a simple graph. For any vertex set $S$ of V, if $G - S$ is acyclic, then $S$ is a decycling set of G; the minimum size of a decyling set is called the decycling number of G, denoted by $\phi \left( G \right)$ . In this paper, we consider the decycling problem of join graphs and obtain the exact value for the decycling number of some types of join graphs. Let ${G_m}$ and ${G_n}$ be simple connected graphs of the order m and n, respectively. Then the decycling number of the join graph ${G_m} \vee {G_n}$ satisfies: $\min \{ m,n\} \leqslant \phi ({G_m} \vee {G_n}) \leqslant $ $ \min \{ m + \phi ({G_n}),n + \phi ({G_m})\}$ . The results presented in this paper confirm that the upper bound for the above inequality is tight. In particular, if ${G_m}$ and ${G_n}$ are trees, then we can obtain the exact value for the decycling number of ${G_m} \vee {G_n}$ .

Key words: graph, decycling number, join graphs

中图分类号: