论文标题
图形的签名边缘支配数字上的上限
Upper bounds on the signed edge domination number of a graph
论文作者
论文摘要
简单图的签名边缘支配函数（或sedf）$ g =（v，e）$是函数$ f：e \ rightArrow \ {1，-1，-1 \} $，以至于$ \ sum_ {e'\ in n [e]} f（e]} f（e]} f（e'} f（e'） $ e $。令$γ_s'（g）$表示所有SEDFS $ f $中$ f（g）$的最小值，其中$ f（g）= \ sum_ {e \ in E} f（e）$。在2005年，Xu undionentuent of une $γ_s'（g）\ le n-1 $，其中$ n $ n $ n $是$ g $ $ g $。在两种情况下，已证明了这一猜想$ v_ {odd}（g）= 0 $和$ v_ {偶}（g）= 0 $，其中$ v_ {odd}（g）$（sesp。$ v_ {evev}（evev}（g）$）是$ g $中的奇数（dect。本文证明了$ v_ {偶}（g）\ in \ {1，2 \} $的Xu的猜想。我们还表明，对于任何简单的图形$ g $，$ n $的$ g $，$γ_s'（g）\ le n+n+v_ {odd}（g）/2 $和$γ_s'（g）\ le n-2+v_ {evev_ {evev} $ n时$ v_ {v_ {v_ {vev}（g）> 0 $ 0 $，以及$γ_s'（$γ_s'（g）'（g）'（g）'（4）。我们的结果改善了$γ_s'（g）\ le \ lceil 3n/2 \ rceil $的最佳当前上限。
A signed edge domination function (or SEDF) of a simple graph $G=(V,E)$ is a function $f: E\rightarrow \{1,-1\}$ such that $\sum_{e'\in N[e]}f(e')\ge 1$ holds for each edge $e\in E$, where $N[e]$ is the set of edges in $G$ that share at least one endpoint with $e$. Let $γ_s'(G)$ denote the minimum value of $f(G)$ among all SEDFs $f$, where $f(G)=\sum_{e\in E}f(e)$.In 2005, Xu conjectured that $γ_s'(G)\le n-1$, where $n$ is the order of $G$. This conjecture has been proved for the two cases $v_{odd}(G)=0$ and $v_{even}(G)=0$, where $v_{odd}(G)$ (resp. $v_{even}(G)$) is the number of odd (resp. even) vertices in $G$. This article proves Xu's conjecture for $v_{even}(G)\in \{1, 2\}$. We also show that for any simple graph $G$ of order $n$, $γ_s'(G)\le n+v_{odd}(G)/2$ and $γ_s'(G)\le n-2+v_{even}(G)$ when $v_{even}(G)>0$, and thus $γ_s'(G)\le (4n-2)/3$. Our result improves the best current upper bound of $γ_s'(G)\le \lceil 3n/2\rceil$.
