具有相同电力控制数与连通控制数的图  

Graphs with Equal Power Domination and Connected Domination Numbers

作　　者：赵小玲[1,2] 吕长虹[2] 

机构地区：[1]上海电机学院数理教学部,上海200240 [2]华东师范大学数学系,上海200062

出　　处：《上海电机学院学报》2012年第6期414-417,共4页Journal of Shanghai Dianji University

基　　金：国家自然科学基金项目资助(60673048;10471044)

摘　　要：令G=(V,E)为简单无向图。若中的所有顶点v均被SV所电力控制,称子集S为G的电力控制集。电力控制数γp(G)为G的所有电力控制集基数的最小值。当图G的控制集S的诱导子图G[S]连通时,称S为连通控制集,图G的连通控制数γc(G)为G的所有连通控制集的基数的最小值。讨论了图G的电力控制数和连通控制数,得到了具有相同电力控制数和连通控制数的仙人掌图、块图、立方图的特征。Let G= （V,E） be a simple undirected graph. A subset S~_C_V is a power dominating set of G if S power dominates all vertices in V. The power domination number, denoted rp（G） , is the minimum cardinality of a power dominating set of G. A dominating set is called a connected dominating set if the induced subgraph GES~ is connected. The connected domination number re（G） of G is the minimum cardinality taken over all minimal connected dominating sets of G. In this paper, we characterize cubic graphs, block graphs and cactus graphs with equal power domi- nation and connected domination numbers.

关 键 词：电力控制数 连通控制数 仙人掌图 块图 立方图 

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