設(shè)G=(V,E)是一個頂點集為V且邊集為E的簡單圖.G的一個符號混合控制函數(shù)定義為函數(shù)f:VUE→{-1,1},使得對每個元素x∈V∪E都有■成立.此處,N_m(x)是V∪E中與x相鄰或關(guān)聯(lián)的所有元素的集合.f的權(quán)為■.G的符號混合控制數(shù)γ_s^*(G)定義為G的所有符號混合控制函數(shù)的最小權(quán).本文中,我們證明了符號混合控制問題在平面圖上是NP-完全的,而且我們求出了完全圖和星圖的符號混合控制數(shù)的精確值.

【文章頁數(shù)】：8 頁

【部分圖文】：

圖1附著到v∈V(G)上的一條邊和一個4-圈

引理2存在H的一個-函數(shù),使得被添加的每條邊和每個4-圈中的元素的函數(shù)值如圖1所示.證設(shè)f是H的一個函數(shù).首先考慮圖1(a)的情況.由f(NHm[u])≥1可知,v,vu,u中的至多一個元素的函數(shù)值為-1.如果f(v)=f(vu)=f(u)=1,則定義如下的函數(shù)9:g(v)=g(....

本文編號：3917226