Roman -domination

详细信息    查看全文

• 作者：Mustapha Chellali^a ; ^{m_chellali@yahoo.com" class="auth_mail" title="E-mail the corresponding author} ; Teresa W. Haynes^b ; ^c ; ^{haynes@etsu.edu" class="auth_mail" title="E-mail the corresponding author} ; Stephen T. Hedetniemi^d ; ^{hedet@clemson.edu" class="auth_mail" title="E-mail the corresponding author} ; Alice A. McRae^e ; ^{aam@cs.appstate.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Roman domination ; Roman {2}{2}-domination ; Weak Roman domination ; 2-rainbow domination ; 2-domination
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 May 2016
• 年：2016
• 卷：204
• 期：Complete
• 页码：22-28
• 全文大小：401 K

文摘

In this paper, we initiate the study of a variant of Roman dominating functions. For a graph G=(V,E)$G=(V,E)$, a Roman {2}$\left\{2\right\}$-dominating function f:V→{0,1,2}$f:V\to \{0,1,2\}$ has the property that for every vertex v∈V$v\in V$ with baf4765c5e17b4088" title="Click to view the MathML source">f(v)=0$f\left(v\right)=0$, either v$v$ is adjacent to a vertex assigned 2 under f$f$, or v$v$ is adjacent to least two vertices assigned 1 under f$f$. The weight of a Roman {2}$\left\{2\right\}$-dominating function is the sum ∑_v∈Vf(v)${\sum }_{v\in V}f\left(v\right)$, and the minimum weight of a Roman {2}$\left\{2\right\}$-dominating function f$f$ is the Roman {2}$\left\{2\right\}$-domination number. First, we present bounds relating the Roman {2}$\left\{2\right\}$-domination number to some other domination parameters. In particular, we show that the Roman {2}$\left\{2\right\}$-domination number is bounded above by the 2-rainbow domination number. Moreover, we prove that equality between these two parameters holds for trees and cactus graphs with no even cycles. Finally, we show that associated decision problem for Roman {2}$\left\{2\right\}$-domination is NP-complete, even for bipartite graphs.