【摘 要】
：
一个稳定集是一个图的相互不相邻的顶点集,一个仙人掌图是一个任意两个圈都没有公共点的连通图.本文我们考虑如下问题,称之为STABLE CACTUS-问题的计算复杂性:给定一个图G,G
【基金项目】
：
国家自然科学基金，湖南省教育规划项目
论文部分内容阅读
一个稳定集是一个图的相互不相邻的顶点集,一个仙人掌图是一个任意两个圈都没有公共点的连通图.本文我们考虑如下问题,称之为STABLE CACTUS-问题的计算复杂性:给定一个图G,G中是否存在稳定集S使得G-S是一个仙人掌图.我们证明了STABLE CACTUS-问题是一个NP-完全问题,甚至可以进一步限制给定的图G是最大度不超过4的偶图.这个结果在图的度条件下是最好的了,我们利用图的最大亏格研究中的Xoung-树方法,证明了如果G是一个最大度不超过3的图,则STABLE CACTUS-问题是多项式时间可解
其他文献
一个图的Hosoya指标是图的所有独立边子集的数目之和,包括空集.T（n1,n2,n3）表示只有一个3度点,三个1度点且唯一3度点到三个一度点的路长分别是n1,n2,n3的树.用代数组合的方法研
振兴辽宁老工业基地需要从国际化的视角来审视,一个工业基地不会孤立于周围的大环境而存续、发展,它的结构调整并不仅仅是开放市场和产业更新.辽宁经济必须面对日趋激烈的市
电视新闻是当今最年轻、最具影响力、观众最广泛的传播媒介.在现今商品经济的社会,电视新闻也要讲究其经济效应.电视新闻要取得收益、获得回报那首先是要让其获得更高的收视
在可持续发展和绿色GDP的背景下,发展环保产业是发展中国家面临的一个共同课题.本文着重归纳了我国环保产业存在的问题,概述了发展我国环保产业的基本取向.
今年的CCBN展会相比以往显得格外热闹,尤其是广电总局被并入国家新闻出版广电总局以后,这将是老广电总局主持召开的最后一届CCBN展会,无论是厂商还是业界专家对于本届展会参
本文对建设项目投资控制中存在的主要问题进行了分析并提出了具体的对策.
研究了一类广泛的随机变量序列NQD列的收敛性质，得到了与独立情形一样的弱大数定律和同分布NQD列的相应结果．
地方高校体育发展根植于区域体育事业发展,应定位于服务区域体育事业,建设好区域体育事业服务平台,在体育人才培养、科技服务、文化引领等方面提供有用、有效和先进的服务。
<正>2014年是全面深化改革元年,在党中央、国务院的坚强领导下,全国就业战线紧密围绕中心、服务大局,扎实工作、狠抓落实,各项就业工作取得了积极进展,就业形势保持总体平稳,