For a graph G, let R(G) and yr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that yr2(G) ≤ R(G) ≤ 3/2yr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which R(G) − yr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs...
We study the concept of an -partition of the vertex set of a
graph , which includes all vertex partitioning problems into
four parts which we require to be nonempty with only external
constraints according to the structure of a model graph , with
the exception of two cases, one that has already been classified
as polynomial, and the other one remains unclassified. In the
context of more general vertex-partition problems, the problems
addressed in this paper have these properties: non-list, -part,
external...
We study the concept of an -partition of the vertex set of a graph , which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph , with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, -part,...
Download Results (CSV)