 |
THE EFFECT OF EDGE LIFTING ON ROMAN DOMINATION IN GRAPHS
Let G be a graph, and let uxv be an induced path centered at x. An edge lift defined on uxv is the
action of removing edges ux and vx while adding the edge uv to the edge set of G. In this paper,
we initiate the study of the effects of edge lifting on the Roman domination number of a graph,
where various properties are established. A characterization of all trees for which every edge lift
increases the Roman domination number is provided. Moreover, we characterize the edge lift of
a graph decreasing the Roman domination number, and we show that there are no graphs with at
most one cycle for which every possible edge lift can have this property.
- Other
