一些卡方积图的符号星控制数
2012-03-09丁宗鹏徐保根张亚琼
丁宗鹏,徐保根,张亚琼
(华东交通大学基础科学学院,江西 南昌,330013)
1 引言及定义
本次研究所考察的图均为无向简单图,文中未说明的符号和术语均与文献[1]相同。
近几年来,图的控制理论的研究内容越来越丰富。加拿大著名图论专家COCKAYNE E J等先后引入了图的许多不同类型的控制概念及其变化形式后,图的控制理论出现了大量的研究成果。然而绝大多数是属于图的点控制,边控制的研究成果还相对较少。在文献[7]中徐保根定义了图的符号边控制概念,并获得了较多的研究成果,随后又从图的符号边控制拓展到了符号星控制上,并得出了一系列的研究成果。笔者在已有成果的基础上又确定了几类特殊图的符号星控制数。
设一个图G=(V,E),v∈V,则v点在G中的边邻域定义为E(v)={uv∈E∣u∈V}。
定义 设G=(V,E)是一个没有孤立顶点的图,如果一个函数f:E→{+1,-1},对一切v∈V(G)满足)≥1成立,则称f为图G的一个符号星控制函数。图G的符号星控制数定义为γ'ss(G)=minf为G的符号星控制函数}。
为了方便,如果f为G的一个符号星控制函数,则称满足f(e)=1的边e是在f下的1边;同样称满足f(e)=-1的边e是在f下的-1边。
2 主要结果及其证明
定理1 对于图G=Pm×Pn,当m,n为奇数且均大于1时,γ'ss(Pm×Pn)=mn-m-n+7。当m,n不全为奇数且均大于1时,γ'ss(Pm×Pn)=mn-m-n+4。
证明 情形1 当m,n全为奇数且均大于1时,对于图G中其度数d(v)=2的点所关联的边均标号1。对于图G中其度数d(v)=3或4的点(共(mn-4)个),依据符号星控制的定义,每个点至多邻接1条-1边,从而图G中至多有(-1)条-1边(如果图G中至少有即为条边标号-1,那么至少存在一个点邻接了2条-1边,这不满足符号星控制的定义,矛盾)。……
