具有3-部极小公平划分的树
2013-11-14孙德荣
孙德荣
(昌吉学院数学系 新疆 昌吉 831100)
1 引言
本文考虑的都是简单无向图.通常用A=A(G)表示图G邻接矩阵,如果图G有n个顶点,V={v1,v2,…,vn} 表示图G的顶点集.如果 π=(C1,C2,…,Ck)是顶点集 V(G)的一个剖分,即V(G)=C1⋃C2⋃…⋃Ck,且Ci⋂Cj=φ(i≠j,1≤i,j≤k),这里Ci称为划分π的一个单元.对任意v∈Ci(1≤i≤k),用NCj(v)={u∈Cj|uv∈E(G)}表示v在Cj中的邻点集,如果对Ci(1≤i≤k)中的任意顶点v,dij(v)=|NCj(v)|是常数(Cj中的点对Ci中的任意顶点v的度的贡献),则称π=(C1,C2,…,Ck)是图G的一个k-部公平划分,每个图都至少存在一个k-部公平划分,事实上,如果V(G)=(v1,v2,…,vn)是图G的顶点集,那么令Ci={Vi}(1≤i≤n),显然π=(C1,C2,…,Cn)是图G的n-部公平划分,一般来说,一个图的公平划分是不唯一的,例如,图1

令C1={v1,v5},C2={v2,v6},C3={v3,v8},C4={v4,v7},容易验证π=(C1,C2,C3,C4)与π′=(C1,C2,C3⋃C4)都是图1的公平划分。图的公平划分在图的结构的研究中有着广泛的应用,我们知道图的特征值是图的不变量,它是刻画图的特征的一个重要指标。如果图G的特征值入对应的某个特征向量的分量和不为零,则入称为图G的主特征值。而图的主特征值是图的闭道数的主要参数,与图的结构有很大的关系,例如,只有一个主特征值的图G一定是正则图([1]),这类图具有1-部公平划分。Y.Hou和H.Zhou([2])找到了所有的恰有两个主特征值的树,分别是:调和树Ta(a≥2)、星S1,n和双星Sn+1,n+1,Y.Hou和F.Tian([3])还证明了恰有两个主特征值的所有单圈图是Clk,而这些图除了调和树Ta(a≥2)以外都恰好具有2-部公平划分。孙德荣([4]-[5])证明了顶点集具有二部公平划分的图都恰好有两个主特征值,并且通过对某些具有3-部公平划分的树的研究发现,这些树又都恰好有三个主特征值,而Hagos([6])证明了一个图G的主特征值的个数m(G)等于G的walk-矩阵W(G)的秩,于是孙……
