关于几乎边缘图的研究

刘海琼

【摘要】图的中心集C（G）和边缘集P（G）分别是指具有最小离心率的顶点组成的集合和最大离心率的顶点组成的集合.若图G只有一个中心点，其他都是边缘点，则称图G为几乎边缘图（简称AP图），半径为r的AP图称为r-AP图.本文主要是对文献[1]中提出的问题给出结论及构造的方法，给出半径为3的AP图的指标上界.若T是AP图时，则T与K1，n-1同构，最后证明了既是ASC图又是AP图的图是P3.

【关键词】中心集；边缘集；AP图；ASC图；同构

本文中考虑的图都是连通图.在图G中，V（G）、E（G）分别表示其顶点集和边集.顶点数又称为图的阶.当vi，vj∈V（G），vi和vj之间的距离是指在G中连接它们的最短路的长度，用dG（vi，vj）表示.对任意的顶点vi∈V（G），vi的离心率是指在G中vi到其他顶点的最大距离，用εG（vi）表示.G的直径用d（G）表示，它是指G中所有顶点的最大离心率.而G中所有顶点的最小离心率我们称为半径，用r（G）表示.若dG（u，v）=εG（v），則称v是u的离心顶点.当εG（vi）=r（G）时，称vi为G的中心顶点，类似的，若εG（vj）=d（G），则称vj为G的直径顶点.若u∈V（G），则GuH是指图H中每个点都和u相连.GH表示图H中的每一个顶点都和图G中的每一个点相连.T，Km，n，Kn，Pn分别表示树，完全二部图，完全图，路等.

下面定义中心集C（G）和边缘集P（G），即

C（G）={vi∈V（G）|εG（vi）=r（G）}，

P（G）={vi∈V（G）|εG（vi）=d（G）}.

若|C（G）|=|V（G）|-2，则G是几乎自中心图，简称ASC图.若|P（G）|=|V（G）|-1，则图G是几乎边缘图，简称AP图.半径为r的ASC和AP图称为r-ASC和r-AP图.在G中添加最少的顶点构造r-AP图，则G是r-AP图的诱导子图，我们把添加的顶点数，称为r-ASC图和r-AP图的指标，分别用θr（G），Φr（G）表示.即

Φr（G）=min{|V（H）|-|V（G）|：H is r-AP，Ginduced in H}.

在[1]中提出是否存在阶n<4r+1且r≥4的r-AP图的问题？下面给出肯定的回答：

定理1对任意的整数r≥4，存在一个阶为4r的r-AP图.

证明若r≥4，则令Gr的构造如下所述.它的顶点集V（G）={u1，…，u2r+3}∪{v1，…，v2r-3}.

顶点u1，…，u2r+3诱导一个长度为2r+3的圈，顶点u2，…u5，v2r-3，…，v1诱导另一个长度为2r+1的圈，并且顶点vr-1连接ur+5.如图所示.

下面我们证明G是r-AP图.首先注意到vr-1既在圈长为2r的圈中，又在圈长为2r+1的圈中，所以eG（vr-1）=r.事实上由于顶点u1，…，u2r+3诱导的一个圈的长度为2r+3所以我们立刻可以得出顶点u1，…，u2r+3的离心率都是r+1.若1≤i≤r-3，则对任意的顶点vi，有dG（vi，ur-i+4）=dG（vi，ur-i+3）=r+1，从而eG（vi）=r+1，当i=r-2时，dG（vi，ur-i+4）=r+1即eG（vi）=r+1.由图的对称性可得，对于r≤i≤2r-3，eG（vi）=r+1.故综上所述，即C（G）={vr-1}，P（G）=V（G）＼{vr-1}.

因此，|V（G）|=（2r+3）+（2r-3）=4r，定理2.2成立.

定理2若图G是至少有两个点的任意图，则Φ2（G）≤5，等号成立当且仅当图G是完全图.

定理3若图G是包含K3作为其诱导子图的任意图，则Φ3（G）≤9.

定理4如果图G是一个r-AP图，r≥1，u是图G的中心顶点，则对任意的图H，GuH是r-AP图.

由定理4很容易得到下面两个推论.

推论5若r≥2，则K1r-SC是1-AP图.

推论6若图G是半径r≥2的图，则K1G是1-AP图.

引理7令图的半径为r，直径为d，对任意的整数k，r≤k≤d，则至少存在两个点的离心率为k.

定理8若树T是AP图，则T≌K1，n-1.

定理9若图G既是ASC图又是AP图，则图G是P3.

【参考文献】

[1]S Klaar，K P Narayankar，H B Walikar，S B Lokesh.Almost-peripheral graphs[J].Taiwanese J.Math，2014，18：463-471.

[2]S Klavar，K P Narayankar，H B Walikar.Almost self-centered graphs[J].Acta Math.Sin.（Engl.Ser.），2011，27：2343-2350.

[3]L Lesniak.Eccentric sequence in graphs[J].Period.Math，Hung，1975，6：287-293.