有向路和有向圈的控制集数  

TOTAL NUMBERS OF DOMINATING SETS OF DIRECTED PATHS AND DIRECTED CYCLES

作　　者：罗永萍[1] 杨爱民[1] 

机构地区：[1]山西大学数学科学学院,太原030006

出　　处：《高等学校计算数学学报》2007年第1期74-79,共6页Numerical Mathematics A Journal of Chinese Universities

基　　金：国家自然科学基金(10471081);山西省自然科学基金(20031003)

摘　　要：设G=（V,E）为无向图．子集D真包含于V（G）是无向图G的控制集，如果对于任意的Y∈V（G）-D，都存在x∈D，使xy∈E（G）．G的控制集D是G的分裂控制集，如果G中由V（G）-D导出的子图G（V（G）-D）是不连通的．G的一个控制集D是G的一个强（弱）控制集，若da（x）≥da（y）（da（x）≤dG（y）），其中da（x）表示G中与点x关联的边数．Numerous papers are presented for the properties of the dominating sets, the split dominating sets, the strong（weak） dominating sets of graphs. In this paper, the recurrence relations of total numbers of three kinds of the dominating sets of directed path Pn （n ≥ 1） and directed cycle Cn （n ≥ 3） are given.Specially, for total numbers of the dominating sets and the strong（weak） dominating sets of Pn and Cn. The recurrence relations are identical to Fibonacci sequence.

关 键 词：控制集 有向圈 有向路 无向图 子集 分裂 连通 子图 

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