星划分数的计算复杂性及其与支配数的联系  

Complexities of Star Partition Number and Its Connections with Domination Number

作　　者：蔡延光[1] 张新政[1] 

机构地区：[1]广东工业大学自动化学院,广东广州510090

出　　处：《广东工业大学学报》2002年第3期25-29,共5页Journal of Guangdong University of Technology

基　　金：广东省科技攻关资助项目(C31801);广东省自然科学基金资助项目(010060).

摘　　要：分别证明了"确定任意无向简单图星划分数与支配数是否相等"、"求二分平面图的星划分数"与"任意无向简单图的星划分数是否等于3"It is shown to determine whether the domination munber is equal to the star partition number for any undirected simple graph is NPcomplete,which is an open problem proposed by Laskar,Walikar.The author also proves that computing the star partition number for any bipartite planar graph is NPcomplete,and determining whether the star partition number is equal to 3 for any undirected simple graph is NPcomplete respectively.

关 键 词：星划分数 支配集 支配数 计算复杂性 NP-完全 图论 任意无向简单图 

分 类 号：O157.5[理学—数学]