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

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

【部分圖文】：

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

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

本文編號(hào)：3917226