摘要
单圈图是边数等于顶点数的连通图.令G=(V,E)是无孤立顶点的图,若集合DV(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.
出处
《宁夏大学学报（自然科学版）》
CAS
2014年第4期311-314,323,共5页
Journal of Ningxia University(Natural Science Edition)
关键词
私有k-距离邻集
k-距离匹配控制数
单圈图
private k-distance neighborhood
k-distance paired domination number
unicyclic graphs
