Total Roman domination on Kneser graphs

A Roman dominating function (RDF) on a graph G is a function f : V (G) \longrightarrow \{۰, ۱, ۲\} such that any vertex v with f(v) = ۰ is adjacent to at least one vertex w with f(w) = ۲. In addition, if the subgraph of G induced by the set of all vertices for which f \ne ۰ has no isolated vertices then f is called a total Roman dominating function (TRDF). If f is an RDF (TRDF) then the least value of \sum_{u\in V} f(u) is called Roman domination number (total Roman domination number) of G and is denoted by \gamma_{_R}(G) ( \gamma_{_{tR}}(G)). Let G=G(n, k, ۰) be a Kneser graph, where n,k are positive integers. In this paper we present some bounds for \gamma_{_{tR}}(G(n, k, ۰)) for k^۲ < n < k^۲+k. In particular we show that \gamma_{_{tR}}(G(k^۲+k-۱, k, ۰))=۲(k+۲) and for n\geqslant ۲k+۱, \gamma_{_{R}}(G(n, k, ۰)) \geq max \{ \gamma_{_{R}}(G(n-۱, k -۱, ۰)), \gamma_{_{R}}(G(n, k -۱, ۰))\}.

کلیدواژه ها:

total Roman domination number ، Kneser Graph