关于图的反符号边控制

On Reverse Signed Edge Domination in Graphs

引入了图的反符号边控制的概念,设G=(V,E)是一个图,一个函数f:e→{-1,+1}如果对任意e∈E(G),均有∑e′∈N[e]f(e′)≤0,则称f为图G的一个反符号边控制函数.图G的反符号边控制数定义为-γs(G)=max{∑e∈Ef(e)|f为图G的反符号边控制函数}.在本文中,我们主要给出了图的反符号边控制数的两个上界,并确定了几类特殊图的反符号控制函数.

In this paper we introduce the concept of minus edge domination in graphs. Let G = （V, E）be a graph, a function f：E→{-1,＋1} is said to be a reverse signed dominating function （RSEDF） of G if ∑e′∈Nf（e′）≤0 holds for everyedge e∈E, the reverse signed domination number of G is defined asγs（G）=max{∑e∈Ef（e）｜f｜ is a RSEDF of G }. In this paper we obtain two upper bounds of rs（G） for general graphs G,and determine the exact values of rs（G） for some special classes of graphs G.