| Constructive characterizations of （γp, γ）- and （γp, γpr）-trees |
| |
| 作者姓名： | CHEN Lei ;LU Chang-hong ;ZENG Zhen-bing |
| |
| 作者单位： | [1]Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai200062, China; [2]Department of Mathematics, East China Normal University, Shanghai 200062, China |
| |
| 基金项目： | Supported in part by National Natural Science Foundation of China （60673048; 10471044）; National Basic Research Program （2003CB318003）; Shanghai Leading Academic Discipline Project （B407） |
| |
| 摘 要： | Let G = （V, E） be a graph without isolated vertices. A set S lohtain in V is a domination set of G if every vertex in V - S is adjacent to a vertex in S, that is NS] = V. The domination number of G, denoted by γ（G）, is the minimum cardinality of a domination set of G. A set S lohtain in V is a paired-domination set of G if S is a domination set of G and the induced subgraph GS] has a perfect matching. The paired-domination number, denoted by γpr（G）, is defined to be the minimum cardinality of a paired-domination set S in G. A subset S lohtain in V is a power domination set of G if all vertices of V can be observed recursively by the following rules： （i） all vertices in NS] are observed initially, and （ii） if an observed vertex u has all neighbors observed except one neighbor v, then v is observed （by u）. The power domination number, denoted by γp（G）, is the minimum cardinality of a power domination set of G. In this paper, the constructive characterizations for trees with γp=γ and γpr = γp are provided respectively.
|
| 关 键 词： | 功率控制 偶控制 树 控制集 |
Constructive characterizations of (γ
p
, γ)- and (γ
p
, γ
pr
)-trees |
| |
| CHEN Lei,;LU Chang-hong,;ZENG Zhen-bing.Constructive characterizations of (γ
p
, γ)- and (γ
p
, γ
pr
)-trees[J].Applied Mathematics A Journal of Chinese Universities,2008,23(4):475-480. |
| |
| Authors: | Lei Chen Chang-hong Lu Zhen-bing Zeng |
| |
| Institution: | (1) Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, 200062, China;(2) Department of Mathematics, East China Normal University, Shanghai, 200062, China |
| |
| Abstract: | Let G = (V, E) be a graph without isolated vertices. A set S ⊆ V is a domination set of G if every vertex in V - S is adjacent to a vertex in S, that is NS] = V. The domination number of G, denoted by γ(G), is the minimum cardinality of a domination set of G. A set S ⊆ V is a paired-domination set of G if S is a domination set of G and the induced subgraph GS] has a perfect matching. The paired-domination number, denoted by γ
pr
(G), is defined to be the minimum cardinality of a paired-domination set S in G. A subset S ⊆ V is a power domination set of G if all vertices of V can be observed recursively by the following rules: (i) all vertices in NS] are observed initially, and (ii) if an observed vertex u has all neighbors observed except one neighbor v, then v is observed (by u). The power domination number, denoted by γ
p
(G), is the minimum cardinality of a power domination set of G. In this paper, the constructive characterizations for trees with γ
p
= γ and γ
pr
= γ
p
are provided respectively.
Supported in part by National Natural Science Foundation of China (60673048; 10471044); National Basic Research Program (2003CB318003);
Shanghai Leading Academic Discipline Project (B407) |
| |
| Keywords: | domination power domination paired-domination tree |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
|
