2021/01/16 by Kijung Kim, Kim, Kijung
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2101.06546
openalex publication_date 2021/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a graph. A subset D of V is a restrained dominating set if every vertex in V ∖ D is adjacent to a vertex in D and to a vertex in V ∖ D. The restrained domination number, denoted by γr(G), is the smallest cardinality of a restrained dominating set of G. A function f : V → \0, 1, 2\ is a restrained Italian dominating function on G if (i) for each vertex v ∈ V for which f(v)=0, it holds that ∑u ∈ NG(v) f(u) ≥ 2, (ii) the subgraph induced by \v ∈ V | f(v)=0 \ has no isolated vertices. The restrained Italian domination number, denoted by γrI(G), is the minimum weight taken over all restrained Italian dominating functions of G. It is known that γr(G) ≤ γrI(G) ≤ 2γr(G) for any graph G. In this paper, we characterize the trees T for which γr(T) = γrI(T), and we also characterize the trees T for which γrI(T) = 2γr(T).