单圈图的k-距离匹配控制数  

k-distance Paired Domination Number of Unicyclic Graph

作　　者：侯睿[1] 

机构地区：[1]宁夏大学教育学院,宁夏银川750021

出　　处：《宁夏大学学报（自然科学版）》2014年第4期311-314,323,共5页Journal of Ningxia University(Natural Science Edition)

摘　　要：单圈图是边数等于顶点数的连通图.令G=(V,E)是无孤立顶点的图,若集合DV(G)是G的一个k-距离控制集且导出子图〈D〉有完美匹配,则称D是G的一个k-距离匹配控制集.k-距离匹配控制数γkp(G)是G的最小k-距离匹配控制集的势.主要证明了单圈图k-距离匹配控制数的一个重要引理,由此找到了单圈图k-距离匹配控制数的上界,并构造了极图.An unicyclic graph is a connected graph whose vertices number equals to edges number.LetG=（V,E）be a graph without an isolated vertex.A set D∈V（G）is a k-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph〈D〉has a perfect matching.The k-distance paired domination number is the cardinality of a smallest k-distance paired dominating set of G.In this paper,a lemma of the k-distance number of unicyclic graphs is proved.Based on the lemma,an upper bound on the k-distance paired domination number of unicyclic graphs is presented,and the extremal unicyclic graphs are also characterized.

关 键 词：私有k-距离邻集 k-距离匹配控制数 单圈图 

分 类 号：O158[理学—数学]