关于组合星图反馈结点集的下界
On lower bound of feedback vertex set of (n,k)-star graph
-
摘要: 最近诸多文章旨在讨论关于反馈结点集的上下界问题,比如:蝴蝶网、超立方体、网格、星图等等.本文主要讨论了关于组合星图反馈结点集的下界问题,在基于组合星图的性质和已有相关结果的基础上,给出了组合星图反馈结点集的新的下界.Abstract: Aseries of recent papers has ai med at giving good bounds of feedback vertex set for families of graphsbroadly known as: butterflies,hypercubes,meshes,star graphs,and so on.Compare to existing results for generalgraph,newlower bound onthe size of the mini mumfeedback vertexset of (n,k)-star graphis given based onits spe-cial structure.