On the Roman domination subdivision number of a graph (Q782761): Difference between revisions
From MaRDI portal
Latest revision as of 04:50, 23 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Roman domination subdivision number of a graph |
scientific article |
Statements
On the Roman domination subdivision number of a graph (English)
0 references
29 July 2020
0 references
Let \(G\) be a graph and let \(V_0\), \(V_1\), \(V_2\) be a partition of \(V(G)\). Such a partition is a Roman partition if every vertex from \(V_0\) has a neighbor in \(V_2\). The Roman domination number is \(\gamma_R(G)=\min\{2|V_2|+|V_1|\}\), where the minimum is taken over all Roman partitions of \(G\). Further, the Roman domination subdivision number, denoted by \(\mathrm{sd}_{\gamma_R}(G)\), is the minimum number of edges of \(G\) that needs to be subdivided by one vertex, such that the Roman domination number of the new graph exceed \(\gamma_R(G)\). The present work is a two results paper. In the first the authors succeed to improve the upper bound on \(\mathrm{sd}_{\gamma_R}(G)\), that is \[\mathrm{sd}_{\gamma_R}(G)\leq 3+\min\{\mathrm{deg}_2(v):v\in V(G)\wedge {\deg}(v)\geq 2\},\] where \(\mathrm{deg}_2(v)\) represents the number of vertices at distance two to \(v\). The result on complexity follows. In particular, it is proven that the problem of determining \(\mathrm{sd}_{\gamma_R}(G)\) is NP-hard for bipartite graphs. The reduction is done from 3SAT.
0 references
Roman domination
0 references
Roman domination subdivision number
0 references