资源描述：
《关于几乎边缘图的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、关于几乎边缘图的研究【摘要】图的中心集C(G)和边缘集P(G)分别是指具有最小离心率的顶点组成的集合和最大离心率的顶点组成的集合•若图G只有一个中心点，其他都是边缘点，则称图G为几乎边缘图(简称AP图)，半径为r的AP图称为r-AP图.本文主要是对文献［1］中提出的问题给出结论及构造的方法，给出半径为3的AP图的指标上界•若T是AP图时，则T与K1,n-l同构，最后证明了既是ASC图又是AP图的图是P3.【关键词】中心集；边缘集；AP图；ASC图；同构本文中考虑的图都是连通图•在图G中，V(G)、E(G)分别表示其顶点集和边集•顶点
2、数乂称为图的阶•当vi,vjev(G),vi和vj之间的距离是指在G屮连接它们的最短路的长度，用dG(vi,vj)表示•对任意的顶点viGV(G),vi的离心率是指在G中vi到其他顶点的最大距离，用eG(vi)表不.G的直径用d(G)表不，它是指G中所有顶点的最大离心率•而G中所有顶点的最小离心率我们称为半径，用r(G)表示•若dG(u,v)=eG(v),?t称v是u的离心顶点•当£G(vi)=r(G)时，称vi为G的中心顶点，类似的，若£G(vj)=d(G),则称vj为G的直径顶点.若uWV(G),则GuH是指图H中每个点都和u相
3、连・GH表示图H中的每一个顶点都和图G屮的每一个点相连・T,Km,n,Kn,Pn分别表示树，完全二部图，完全图，路等.下面定义中心集C(G)和边缘集P(G),即C(G)={viGV(G)
4、eG(vi)二r(G)},P(G)={vieV(G)
5、eG(vi)=d(G)}.若
6、C(G)h
7、V(G)
8、-2,则G是几乎自中心图，简称ASC图.若
9、P(G)
10、=
11、V(G)
12、-1,则图G是几乎边缘图，简称AP图•半径为t的ASC和AP图称为r-ASC和r-AP图•在G屮添加最少的顶点构造r-AP图，则G是r-AP图的诱导子图，我们把添加的顶点数，称
13、为r-ASC图和r-AP图的指标，分别用9r(G),①r(G)表示•即0r(G)=min{
14、V(H)
15、-
16、V(G)
17、：Hisr-AP,GinducedinH}.在［1］中提岀是否存在阶n<4r+lJBLr^4的“AP图的问题？下面给出肯定的回答：定理1对任意的整数r^4,存在一个阶为4r的r-AP图.证明若r^4,则令Gr的构造如下所述•它的顶点集V(G)={ul,…,u2r+3}U{vl,…，v2r~3}.顶点ul,…，u2r+3诱导一个长度为2r+3的圈，顶点u2,・・・u5,v2r-3,・・・，vl诱导另一个长度为2r+l的圈
18、，并且顶点vr-1连接wr+5.如图所示.下面我们证明G是r-AP图.首先注意到vr-1既在圈长为2r的圈中，又在圈长为2r+l的圈中，所以eG(vr-1)二r.事实上由于顶点ul,…，u2r+3诱导的一个圈的长度为2r+3所以我们立刻可以得出顶点ul,・・・，u2r+3的离心率都是r+1•若1WiWr-3,则对任意的顶点vi,有dG(vi,ur-i+4)=dG(vi,ur-i+3)=r+l,从而cG(vi)=r+l,当i=r-2时，dG(vi,ur~i+4)=r+l即eG(vi)=r+l.由图的对称性可得，对于rWiW2r-3,e
19、G(vi)二r+1.故综上所述，即C(G)={vr-l},P(G)二V(G){vr-1}.因此，
20、V(G)
21、=(2r+3)+(2r-3)=4r,定理2.2成立.定理2若图G是至少有两个点的任意图，则①2(G)W5,等号成立当口仅当图G是完全图.定理3若图G是包含K3作为其诱导子图的任意图，则①3(G)W9.定理4如果图G是一个r-AP图，r^l,u是图G的中心顶点，则对任意的图H,GuH是r-AP图.由定理4很容易得到下面两个推论.推论5若&2,则Klr-SC是1-AP图.推论6若图G是半径r^2的图，贝I」K1G是1-AP图.引
22、理7令图的半径为「直径为d,对任意的整数k,rWkWd,则至少存在两个点的离心率为k.定理8若树T是AP图，则T9K1,n-1.定理9若图G既是ASC图又是AP图，则图G是P3.【参考文献】[1]SK1aar,KPNarayankar,HBWalikar,SBLokesh・Almost-peripheralgraphs[J]・TaiwaneseJ.Math,2014,18：463-471.[2]SKlavar,KPNarayankar,IIBWalikar.Almostself-centeredgraphs[J].ActaMath.
23、Sin.(Engl.Ser.),2011,27：2343-2350.[3]LLesniak.Eccontricsequenceingraphs[J]・Period.Math,Hung,1975,6：287-293.
