关于几乎边缘图的研究.doc

《关于几乎边缘图的研究.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关于几乎边缘图的研究【摘要】图的中心集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(

2、G)分别表示其顶点集和边集.顶点数乂称为图的阶.当vi，vj^V(G)，vi和vj之间的距离是指在G屮连接它们的最短路的长度，用dG(vi，vj)表示.对任意的顶点vi^V(G),vi的离心率是指在G中vi到其他顶点的最大距离，用€G(vi)表7K.G的直径用d(G)表不，它是指G中所為顶点的最大离心率.而G中所有顶点的最小离心率我们称为半径，用r(G)表示.若dG(u,v)=eG(V)，？t称v是u的离心顶点.当eG(vi)=r(G)时，称vi为G的中心顶点，类似的，若eG(vj)=d(G),则称v

3、j为G的直径顶点.若uev(G)，贝UGull是指图H中每个点都和u相连.G1I表示图11中的每一个顶点都和图G屮的每一个点相连.T，Km，n，Kn，Pn分别表示树，完全二部图，完全图，路等.下面定义中心集C(G)和边缘集P(G),即C(G)={viev(G)

4、eG(vi)二r(G)}，P(G)={viev(G)

5、eG(vi)=d(G)}.若

6、C(G)

7、=

8、V(G)

9、-2,则G是几乎自中心图，简称ASC图.若

10、P(G)I二

11、V(G)卜1，则图G是几乎边缘图，简称AP图.半径为r的ASC和AP图称为r-

12、ASC和r-AP图.在G屮添加最少的顶点构造r_AP图，则G是r-AP图的诱导子图，我们把添加的顶点数，称为r-ASC图和r-AP图的指标，分别用0r(G),®r(G)表示.BPOr(G)=min{

13、V(H)(G):Hisr-AP,GinducedinH}.在［1］中提出是否存在阶n<4r+l且r彡4的r_AP图的问题？下面给出肯定的回答：定理1对任意的整数r>4,存在一个阶为4r的r-AP图.证明若r彡4，则令Gr的构造如下所述.它的顶点集V(G)={ul，…，u2r+3}U{vl,…，v2r~3}

14、.顶点ul，…，u2r+3诱导一个长度为2r+3的圈，顶点u2，-u5,v2r_3，…，vl诱导另一个长度为2r+l的圈，并且顶点vr_l连接ur+5.如图所示.下面我们证明G是r-AP0.首先注意到vr-1既在圈长为2r的圈中，又在圈长为2r+l的圈中，所以eG(vr-1)=r.事实上由于顶点ul，…，u2r+3诱导的一个圈的长度为2r+3所以我们立刻可以得出顶点ul，…，u2r+3的离心率都是r+1.若l

15、+l,从而eG(vi)=r+l,当i=r-2时，dG(vi,ur~i+4)=r+lBPeG(vi)=r+l.由图的对称性可得，对于r

16、V(G)

17、=(2r+3)+(2r-3)=4r,定理2.2成立.定理2若图G是至少有两个点的任意图，则02(G)<5,等号成立当且仅当图G是完全图.定理3若图G是包含K3作为其诱导子图的任意图，则03(G)<9.定理4如果图G是一个r-AP图，r彡1,ii是

18、图G的中心顶点，则对任意的图H，GuH是r-AP图.由定理4很容易得到下面两个推论.推论5若r彡2，则Klr-SC是1-AP图.推论6若图G是半径r彡2的图，贝ijK1G是1-AP图.引理7令图的半径为r,直径为d,对任意的整数k,r^k^d,则至少存在两个点的离心率为k.定理8若树T是AP图，则TSK1,n-1.定理9若图G既是ASC图又是AP图，则图G是P3.【参考文献】[1]SK1aar,KPNarayankar,HBWalikar,SBLokesh.Almost-peripheralgraph

19、s[J].TaiwaneseJ.Math，2014,18：463-471.[1]SKlavar,KPNarayankar,IIBWalikar.Almostself-centeredgraphs[J].ActaMath.Sin.(Engl.Ser.)，2011,27：2343-2350.[2]LLesniak.Eccentricsequenceingraphs[J].Period.Math,Hung,1975,6：287-293.