On the Roman domination subdivision number of a graph

摘要

A Roman dominating function (RDF) of a graph G is a labeling f : V(G) -> {0, 1, 2} such that every vertex with label 0 has a neighbor with label 2. The weight of an RDF is the sum of its functions values over all vertices, and the Roman domination number of G is the minimum weight of an RDF of G. The Roman domination subdivision number sd(gamma R) (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number of G. In this paper, we present a new upper bound on the Roman domination subdivision number by showing that for every connected graph G of order at least three,