科研之友
微信
新浪微博
Facebook
分享链接
摘要
设图G=（V, E）,对于V中任何一个点集S,若G-S是一个无圈图,则称S是图G的一个消圈集,且称min{|S||S是图G的消圈集}为图G的消圈数,记为φ（G）.本文考虑联图的消圈问题,得到了几类联图消圈数的精确值.设Gm和Gn分别表示阶数为m和n的简单连通图,则联图Gm∨Gn的消圈数满足:min{m, n}≤φ（Gm∨Gn）≤min{m+φ（Gn）, n+φ（Gm）}.文中几类联图的消圈数证实了上述不等式的上界是紧的.特别地,当Gm和Gn都为树时，可由不等式直接得到φ（Gm∨Gn）的精确值.
- 单位
