关于图的符号混合控制

发布时间：2024-03-02 18:30

　　设G=(V,E)是一个顶点集为V且边集为E的简单图.G的一个符号混合控制函数定义为函数f:VUE→{-1,1},使得对每个元素x∈V∪E都有■成立.此处,N_m(x)是V∪E中与x相邻或关联的所有元素的集合.f的权为■.G的符号混合控制数γ_s^*(G)定义为G的所有符号混合控制函数的最小权.本文中,我们证明了符号混合控制问题在平面图上是NP-完全的,而且我们求出了完全图和星图的符号混合控制数的精确值.

【文章页数】：8 页

【部分图文】：

图1附着到v∈V(G)上的一条边和一个4-圈

引理2存在H的一个-函数,使得被添加的每条边和每个4-圈中的元素的函数值如图1所示.证设f是H的一个函数.首先考虑图1(a)的情况.由f(NHm[u])≥1可知,v,vu,u中的至多一个元素的函数值为-1.如果f(v)=f(vu)=f(u)=1,则定义如下的函数9:g(v)=g(....