刘　凌

(上海理工大学 理学院,上海　200093)



Wenger图的控制数

刘凌

(上海理工大学 理学院,上海200093)

1问题的提出

这些结论对于研究极值图论中偶圈的Turán数的精确阶都有十分重要的意义[4-6].在文献[7]中,Viglione确定了Hm(q)的直径(图中任意两点间距离的最大值).受此启发,本文将研究Hm(q)的另一个结构参数——控制数.

首先给出Wenger图Hm(q)和控制数的定义.

定义2[8-10]设G=(V,E)为一个图,D⊆V,若对每一个v∈VD,存在u∈D,使uv∈E,则称D为图G的一个控制集,G的控制数

定义3设G=(X∪Y,E)为一个二部图,M⊆X,若对于每个v∈Y,存在u∈M,使uv∈E,则称M为Y在X中的一个控制集,Y在X中的控制数

同样,可定义X在Y中的控制数

易见,二部图G的控制数

设v是图G中的一个点,G中与点v相关联的边的条数称为点v的度,用d(v)表示.下面的命题1在文献[1]中已有证明,为了文章的完整性,这里给出了它的另一种证明.

命题1在Hm(q)中,对任意的A∈X,B∈Y,都有A与B的度相等,都为q.

证明由Hm(q)图中AB相邻的定义,可知A的度必为q,又对任意B=[b1,b2,…,bm]T∈Y,若A=[a1,a2,…,am]T∈X，A与B相连,则a1,a2,…,am为方程组

(1)

的解,其系数矩阵

的秩为m-1,从而方程组(1)的解空间维数为1,故X中恰有q个点与B相连,B的度也为q.

2Wenger图Hm(q)的控制数

通过构造Hm(q)的一个控制集,并证明其是点数最小的控制集,从而确定Hm(q)的控制数.

引理1设a∈Fq,Hm(q)=(X∪Y,E),

则M中任意两个不同的点都没有公共邻点.

故有

从而a1,m-1-a2,m-1=0,a1,m-2-a2,m-2=0,…,依此类推,a11-a21=0,故a1j=a2j,j=1,2…,m-1,即A1=A2,矛盾.

命题2设a∈Fq,则M={[a1,…am-1,a]T|a1,…,am-1∈Fq}⊆X为Hm(q)中Y在X中的控制集,并且Y在X中的控制数为qm-1.

证明由命题1,X中每一个点的度为q,M中共有qm-1个点,每个点的度均为q.又由下面的引理2可知,M中不同的A点一定与Y中不同的B点相连,从而Y中所有qm个点与M中点相连且没有重复……