论文部分内容阅读
设图G=(V,E)。一个符号外边控制函数是这样的函数f:E→{-1,1},对任一e∈E(G),有f(O(e))=∑e′∈O(e)f(e′)≥1,这里O(e)是e的闭邻域的补。f的权ω(f)定义为G的所有边的函数值的和。G的所有符号外边控制函数中最小的权定义为G的符号外边控制数,记作γ′SOE(G)。文章建立了图的符号外边控制数的一个下界,即γ′SOE(G)≥ δ-△+1/m+1- δ-△m,确定了几类特殊图的符号外边控制数。