Independent Roman {2}-Domination in Trees

LI Bei-bei, SHANG Wei-ping

doi:10.13371/j.cnki.chin.q.j.m.2022.04.006

Chinese Quarterly Journal of Mathematics >

2022 , Vol. 37 >Issue 4: 386 - 393

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2022.04.006

Independent Roman {2}-Domination in Trees

Expand

1. School of Puyang Innovation High School, Puyang 457000, China; 2. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China

LI Bei-bei (1993-), female, native of Puyang, Henan, teaches at Puyang Innovation High School; SHANG Wei-ping (1980-), female, native of Kaifeng, Henan, associate professor of Zhengzhou University, engages in graph theory.

Received date: 2022-11-14

Online published: 2022-12-30

Supported by

Supported by National Natural Science Foundation of China (Grant No. 12171440).

Fold

Abstract

For a graph G = (V,E), a Roman {2}-dominating function f :V → {0,1,2} has the property that for every vertex v ∈V with f(v) = 0, either v is adjacent to at least one vertex u for which f(u) = 2, or at least two vertices u₁and u₂ for which f(u₁) =f(u₂) = 1. A Roman {2}-dominating function f = (V₀,V₁,V₂) is called independent if V₁∪V₂ is an independent set. The weight of an independent Roman {2}-dominating function f is the value ω(f) =\sum_v∈V f(v), and the independent Roman {2}-domination number i_{R2}(G) is the minimum weight of an independent Roman {2}-dominating function on G. In this paper, we characterize all trees with i_{R2}(T) =γ(T)+ 1, and give a linear time algorithm to compute the value of i_{R2}(T) for any tree T.

Key words： Domination number; Roman {2}-dominating function; Independent Roman {2}-domination number

Cite this article

LI Bei-bei, SHANG Wei-ping . Independent Roman {2}-Domination in Trees[J]. Chinese Quarterly Journal of Mathematics, 2022 , 37(4) : 386 -393 . DOI: 10.13371/j.cnki.chin.q.j.m.2022.04.006

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article