A Roman dominating function for a (non-weighted) graph $G=(V,E)$, is a function $f:V\rightarrow \{0,1,2\}$ such that every vertex $u\in V$ with $f(u)=0$ has at least {one} neighbor $v\in V$ such that $f(v)=2$. The minimum weight $\sum_{v\in V}f(v)$ of a Roman {dominating function} $f$ on $G$ is called the Roman domination number of $G$ and is denoted by $γ_{R}(G)$. A graph {$G= (V,E)$} together with a positive real-valued weight-function $w:V\rightarrow \mathbf{R}^{>0}$ is called a {\it weighted graph} and is denoted by $(G;w)$. The minimum weight $\sum_{v\in V}f(v)w(v)$ of a Roman {dominating function} $f$ on $G$ is called the weighted Roman domination number of $G$ and is denoted by $γ_{wR}(G)$. The domination and Roman domination numbers of unweighted graphs have been extensively studied, particularly for their applications in bioinformatics and computational biology. However, graphs used to model biomolecular structures often require weights to be biologically meaningful. In this paper, we initiate the study of the weighted Roman domination number in weighted graphs. We first establish several bounds for this parameter and present various realizability results. Furthermore, we determine the exact values for several well-known graph families and demonstrate an equivalence between the weighted Roman domination number and the differential of a weighted graph.


翻译:对于(非加权)图 $G=(V,E)$,一个罗马控制函数是一个函数 $f:V\rightarrow \{0,1,2\}$,使得每个满足 $f(u)=0$ 的顶点 $u\in V$ 至少有一个邻居 $v\in V$ 满足 $f(v)=2$。图 $G$ 上罗马控制函数 $f$ 的最小权重 $\sum_{v\in V}f(v)$ 称为 $G$ 的罗马控制数,记作 $γ_{R}(G)$。一个图 $G= (V,E)$ 连同其正实值权重函数 $w:V\rightarrow \mathbf{R}^{>0}$ 被称为一个加权图,记作 $(G;w)$。图 $G$ 上罗马控制函数 $f$ 的最小权重 $\sum_{v\in V}f(v)w(v)$ 称为 $G$ 的加权罗马控制数,记作 $γ_{wR}(G)$。非加权图的控制数与罗马控制数已被广泛研究,特别是在生物信息学和计算生物学中的应用。然而,用于建模生物分子结构的图通常需要权重才能具有生物学意义。本文首次对加权图中的加权罗马控制数展开研究。我们首先为该参数建立了若干界,并给出了多种可实现性结果。此外,我们确定了若干著名图族的精确值,并证明了加权罗马控制数与加权图的微分之间的等价关系。

0
下载
关闭预览

相关内容

【ICLR2022】GNN-LM基于全局信息的图神经网络语义理解模型
专知会员服务
16+阅读 · 2021年10月4日
专知会员服务
25+阅读 · 2021年7月31日
专知会员服务
50+阅读 · 2021年6月2日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
40+阅读 · 2020年8月22日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
VIP会员
相关VIP内容
【ICLR2022】GNN-LM基于全局信息的图神经网络语义理解模型
专知会员服务
16+阅读 · 2021年10月4日
专知会员服务
25+阅读 · 2021年7月31日
专知会员服务
50+阅读 · 2021年6月2日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
40+阅读 · 2020年8月22日
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
相关基金
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员