眼镜图的谱刻图
2011-12-26吴廷增
吴廷增
(青海民族大学数学与统计学院,青海 西宁 810007)
眼镜图的谱刻图
吴廷增
(青海民族大学数学与统计学院,青海 西宁 810007)
只有与G同构的图才有相同的谱,则称图G是谱唯一确定的.眼镜图是在圈Cp和圈Cq的任意一个顶点之间加一条边构成的图,记为ɡ(p,q).证明了眼镜图是谱唯一确定的.
同谱图;图的谱;特征值
0 引言
在本文中如无特殊说明,我们仅考虑无环、无重边的无向简单图.未定义的符号和术语参见文献[1].对于任意的图G,V(G)={v1,v2,…,vn}表示其顶点集,E(G)表示其边集.对于任意的v∈V(G),用N(v)表示其邻集.用d(vi)表示顶点vi的度,并且用Δ表示图G中顶点的最大度.A(G)表示图G的邻接矩阵.多项式PA(G)(λ)=det(λI-A(G))是图G对应邻接矩阵的特征多项式,记作PA(G)(λ)=λn+a1λn-1+…+an.因为A(G)是实对称矩阵,所以它的特征根都是实数.假设λ1(G)≥λ2(G)≥…≥λn(G)是图G的特征值,那么所有的特征值及相应的重集分别称为图G的谱.其中λ1(G)称为图G的谱半径.
两个图是同谱的是指它们分享相同的谱.如果不存在非同构图H与图G有相同的谱,则称图G是谱唯一确定的.Cn和Pn分别表示n个顶点的圈和路.假设Cp和Cq是两个顶点不交的圈.令v1是Cp的顶点及vl是Cq的顶点.在顶点v1和vl之间插入一条长为l-1的路v1v2…vl,结果图记作ɡ(p,l,q),称为ɡ-图,见图1,这里l>1.在图ɡ(p,l,q)中,特别当l=2时,称其为眼镜图,记作ɡ(p,q),见图2.假设Pr+1,Ps+1和Pt+1是三条不交路,这里r,s,t≥1且它们中至多只有一个等于1.分别将三条路的首尾粘接起来所得的图记为θ(r,s,t),称为θ-图,见图3.

图1 ɡ-图

图2 眼镜图

图3 θ-图
研究图的谱唯一确定性是一个古老而又有趣的问题,迄今为止,仅有很小的一部……