Dynamical 2-domination in Graphs

作者：Eslahchi Ch; Maimani H R; Torabi R; Tusserkani R^*

来源：Ars Combinatoria, 2017, 134: 339-350.

• Nearly perfect sets
• Domination
• 2-domination number

In this paper a domination-type parameter, called dynamical 2-domination number, will be introduced. Let G = (V(G), E(G)) be a graph. A subset D subset of V(G) is called a 2-dominating set in G if every vertex in V(G) \ D is adjacent to at least two vertices in D, and in this paper D is called a dynamical 2-dominating set if there exists a sequence of sets D = V-0 subset of V-1 subset of V-2 subset of center dot center dot center dot subset of V-k = V(G) such that, for each i, Vi-1 is a 2-dominating set in < V-i >, the induced subgraph generated by V-i. Also for a given graph G, the size of its dynamical 2-dominating sets of minimum cardinality will be called dynamical 2-domination number of G and will be denoted by (gamma) over tilde (2)(G) We study some basic properties of dynamical 2-dominating sets and compute (gamma) over tilde (2) (G) for some graph classes. Also some results about (gamma) over tilde (2) of a number of binary operations on graphs are proved. A characterization of graphs with extreme values of (gamma) over tilde (2) is presented. Finally, we study this concept for trees and give an upper bound and a lower bound for dynamical 2-domination number of trees.

• 出版日期2017-7