完全多部图的符号边控制数的界

Bounds of the Signed Edge Domination Number of Complete Multipartite Graphs

中文关键词:  符号边控制  符号边控制数  完全多部图

英文关键词:signed edge domination  signed edge domination number  complete multipartite graph

中文摘要:

      $f: E(G)\rightarrow\{-1,1\}$称为图$G =(V,E)$的一个符号边控制函数 (简称SEDF),如果$f[e]=f(N[e])=\sum_{e'\in N[e]}f(e')\geq1$对于图$G$的每条边$e\in E$都成立. $w(f)=\sum_{e\in E}f(e)$称为函数$f$的权. $G$的符号边控制数$\gamma_{s}\,'(G)$是指$G$的所有符号边控制函数的最小权.本文对完全多部图的符号边控制数进行研究.对于完全$r$-部图, 当$r$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界.

英文摘要:

      A function $f: E(G)\rightarrow\{-1,1\}$ is called a signed edge dominating function (SEDF for short) of $G$ if $f[e]=f(N[e])= \sum_{e'\in N[e]}f(e')\geq1$, for every edge $e\in E(G)$. $w(f)=\sum_{e\in E}f(e)$ is called the weight of $f$. The signed edge domination number $\gamma_{s}\,'(G)$ of $G$ is the minimum weight among all signed edge dominating functions of $G$. In this paper, we initiate the study of this parameter for $G$ a complete multipartite graph. We provide the lower and upper bounds of $\gamma_{s}\,'(G)$ for $G$ a complete $r$-partite graph with $r$ even and all parts equal.