On the Roman domination number of the subdivision of some graphs

A Roman dominating function on a graph G = (V, E) is a function f : V(G) → {۰, ۱, ۲} satisfying the condition that every vertex u for which f(u) = ۰ is adjacent to at least one vertex v for which f(v) = ۲. The weight of a Roman dominating function is the value f(V) = ∑u∈V(G)f(u).The minimum possible weight of a Roman dominating function on G is called the Roman domination number of G and is denoted by γR(G). In this paper, and among some other results, we provide some bounds for the Roman domination number of the subdivision graph S(G) of an arbitrary graph G.Also, we determine the exact value of γR(S(G)) when G is Kn, Kr,s or Kn۱,n۲,...,nk.

کلیدواژه ها:

Roman dominating function ، bipartite graph ، tree