Constructive characterizations of (γ p , γ)- and (γ p , γ pr )-trees
Tóm tắt
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 N[S] = 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 G[S] 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 N[S] 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.
Tài liệu tham khảo
Baldwin T L, Mili L, Boisen M B, et al. Power system observability with minimal phasor measurement placement, IEEE Trans Power System, 1993, 89(2): 707–715.
Blidia M, Chellali M, Haynes T W. Characterizations of trees with equal paired and double domination numbers, Discrete Math, 2006, 306: 1840–1845.
Chen T C E, Kang L, Ng C T. Paired-domination on interval and circular-arc graphs, Disccrete Appl Math, 2007, 155: 2077–2086.
Cockayne E J, Favaron O, Mynhardt C M, et al. A characterization of (γ, i)-trees, J Graph Theory, 2000, 34: 277–292.
Dankelmann P, Hattingh J H, Henning M A, et al. Trees with equal domination and restrained domination numbers, J Global Optim, 2006, 34: 597–607.
Hattingh J H, Henning M A. Characterizations of trees with equal domination parameters, J Graph Theory, 2000, 34: 142–153.
Haynes T W, Hedetniem S M, Hedetniemi S T, et al. Domination in graphs applied to electric power networks, SIAM J Discrete Math, 2002, 15: 519–529.
Haynes T W, Hedetniemi S T, Slater P J. Fundamentals of Domination in Graphs, New York: Marcel Dekker, 1998.
Haynes T W, Hedetniemi S T, Slater P J. Domination in Graphs: Advanced Topics, New York: Marcel Dekker, 1998.
Haynes T W, Slater T W. Paired-domination in graphs, Networks, 1998, 32: 199–206.
Haynes T W, Henning M A, Slater P J. Strong equality of domination parameters in trees, Discrete Math, 2003, 260: 77–87.
Hou X. A characterization of (2γ, γ p)-trees, Discrete Math, in Press.
Qiao H, Kang L, Cardei M, et al. Paired-domination of trees, J Global Optim, 2003, 25: 43–54.
West D B. Introduction to Graph Theory, 2nd ed., NJ: Prentice Hall, Inc., 2001.
Zhao M, Kang L, Chang G J. Power domination in graphs, Discrete Math, 2006, 306: 1812–1816.