图与补图的半径

关于图与补图的直径间存在何种关系已在[1]中给出了一个完整的讨论。本文考察了当原图具有任意不同半径时,补图可能具有怎样的半径。这样就对图与补图的半径问关系给出了一个完整的讨论。定义连通图G中一个点v的联系数e(v)是对于G中所有的u取的max d(u,v)(G).半径r(G)是各个点联系数中最小者。若对于一个点v,e(v)=r(G),v是一个中心点。命题1 图G半径为1的充要条件是补图G~c中含有孤立点。证因r(G)=1,则对G中的中心点v来说,u和V(G)中除v外的每一点均相邻,故G~c中v为孤立点。