On the roman domination problem of some Johnson graphs


Tatjana Zec




A Roman domination function (RDF) on a graph G with a set of vertices V = V(G) is a function f : V → {0, 1, 2} which satisfies the condition that each vertex v ∈ V such that f (v) = 0 is adjacent to at least one vertex u such that f (u) = 2. The minimum weight value of an RDF on graph G is called the Roman domination number (RDN) of G and it is denoted by γ R (G). An RDF for which γ R (G) is achieved is called a γ R (G)-function. This paper considers Roman domination problem for Johnson graphs J n,2 and J n,3. For J n,2 , n ⩾ 4 it is proved that γ R (J n,2) = n − 1. New lower and upper bounds for J n,3 , n ⩾ 6 are derived using results on the minimal coverings of pairs by triples. These bounds quadratically depend on dimension n.