论文部分内容阅读
设G=（V,E）为一个n阶无向简单图,N（v）={u∈V｜uv∈E},k为一个整数（1≤k≤n）。若函数f：V→{-1,1}满足条件：V中至少有k个顶点v,使得f（N（v））≤1成立,则称f为图G的一个负k-子确定函数。称βkD（G）=max{f（V）｜f为图G的负k-子确定函数}为图G的负k-子确定数。文中主要给出了图的负k-子确定数的几个上界,进而推广了Ghameshlou等人在文献[8]中的研究结果。