数学季刊 ›› 2022, Vol. 37 ›› Issue (4): 386-393.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.006

• • 上一篇    下一篇

具有特定独立的罗马2-控制数的树

  

  1. 1. School of Puyang Innovation High School, Puyang 457000, China; 2. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
  • 收稿日期:2022-11-14 出版日期:2022-12-30 发布日期:2022-12-30
  • 通讯作者: LI Bei-bei (1993-), female, native of Puyang, Henan, teaches at Puyang Innovation High School; E-mail: 15237611592@163.com
  • 作者简介: 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.
  • 基金资助:
    Supported by National Natural Science Foundation of China (Grant No. 12171440). 

Independent Roman {2}-Domination in Trees

  1. 1. School of Puyang Innovation High School, Puyang 457000, China; 2. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
  • Received:2022-11-14 Online:2022-12-30 Published:2022-12-30
  • Contact: LI Bei-bei (1993-), female, native of Puyang, Henan, teaches at Puyang Innovation High School; E-mail: 15237611592@163.com
  • About author: 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.
  • Supported by:
    Supported by National Natural Science Foundation of China (Grant No. 12171440). 

摘要: 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 u1 and u2 for which f(u1) =f(u2) = 1. A Roman {2}-dominating function f = (V0,V1,V2) is called independent if V1∪V2 is an independent set. The weight of an independent Roman {2}-dominating function f is the value ω(f) =\sumv∈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. 

关键词: Domination number, Roman {2}-dominating function, Independent Roman {2}-domination number

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 uand u2 for which f(u1) =f(u2) = 1. A Roman {2}-dominating function f = (V0,V1,V2) is called independent if V1∪V2 is an independent set. The weight of an independent Roman {2}-dominating function f is the value ω(f) =\sumv∈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

中图分类号: