Advertisement
Published in:
05-06-2020
On the Roman domination subdivision number of a graph
Published in: Journal of Combinatorial Optimization | Issue 2/2020
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
A Roman dominating function (RDF) of a graph G is a labeling \(f:V(G)\longrightarrow \{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 \(\mathrm {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, where \(\deg _2(v)\) is the number of vertices of G at distance 2 from vertex v. Moreover, we show that the decision problem associated with \(\mathrm {sd}_{\gamma _{R}}(G)\) is NP-hard for bipartite graphs.
$$\begin{aligned} \mathrm {sd}_{\gamma _{R}}(G)\le 3+\min \{\deg _2(v)\mid v\in V\;\mathrm {and} \;d(v)\ge 2\}, \end{aligned}$$