Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871773 | Discrete Applied Mathematics | 2017 | 9 Pages |
Abstract
Let G=(V,E) be a graph of order n and let B(D) be the set of vertices in VâD that have a neighbor in the vertex set D. The differential of a vertex set D is defined as â(D)=|B(D)|â|D| and the maximum value of â(D) for any subset D of V is the differential of G, denoted by â(G). A Roman dominating function of G is a function f:Vâ{0,1,2} such that every vertex u with f(u)=0 is adjacent to a vertex v with f(v)=2. The weight of a Roman dominating function is the value f(V)=âuâVf(u). The minimum weight of a Roman dominating function of a graph G is the Roman domination number of G, written γR(G). Bermudo, et al. proved that these two parameters are complementary with respect to the order n of the graph, that is, â(G)+γR(G)=n. In this work we prove that, for any graph G with order nâ¥9 and minimum degree two, â(G)â¥3γ(G)4, consequently, γR(G)â¤nâ3γ(G)4, where γ(G) is the domination number of G. We also prove that for any graph with order nâ¥15, minimum degree two and without any induced tailed 5-cycle graph of seven vertices or tailed 5-cycle graph of seven vertices together with a particular edge, it is satisfied â(G)â¥5n17, consequently, γR(G)â¤12n17.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sergio Bermudo,