联图的消圈数

摘要：

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

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

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金

在线出版日期：2022-02-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：17-21