Name
Abstract | ||
|---|---|---|
For a graph G, let
$$f:V(G)\rightarrow \mathcal {P}(\{1,2\}).$$
If for each vertex
$$v\in V(G)$$
such that
$$f(v)=\emptyset $$
we have
$$\bigcup \nolimits _{u\in N(v)}f(u)=\{1,2\},$$
then f is called a 2-rainbow dominating function (2RDF) of G. The weight w(f) of a function f is defined as
$$w(f)=\sum _{v\in V(G)}\left| f(v)\right| $$
. The minimum weight of a 2RDF of G is called the 2-rainbow domination number of G, denoted by
$$\gamma _{r2}(G)$$
. The 2-rainbow domination stability,
$$st_{\gamma r2}(G)$$
, of G is the minimum number of vertices in G whose removal changes the 2-rainbow domination number. In this paper, we first determine the exact values on 2-rainbow domination stability of some special classes of graphs, such as paths, cycles, complete graphs and complete bipartite graphs. Then we obtain several bounds on
$$st_{\gamma r2}(G)$$
. In particular, we obtain
$$st_{\gamma r2}(G)\le \delta (G)+1$$
and
$$st_{\gamma r2}(G)\le |V(G)|-\varDelta (G)-1$$
if
$$\gamma _{r2}(G)\ge 3$$
. Moreover, we prove that there exists no graph G with
$$st_{\gamma r2}(G)=|V(G)|-2$$
when
$$n\ge 4$$
and characterize the graphs G with
$$st_{\gamma r2}(G)=|V(G)|-1$$
or
$$st_{\gamma r2}(G)=|V(G)|-3$$
. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s10878-019-00414-0 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
2-Rainbow domination, 2-Rainbow domination number, 2-Rainbow domination stability | Graph,Combinatorics,Vertex (geometry),Bipartite graph,Domination analysis,Rainbow,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 3 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zepeng Li | 1 | 20 | 9.07 |
| Zehui Shao | 2 | 119 | 30.98 |
| Shou-jun Xu | 3 | 0 | 0.34 |