劉海瓊

【摘要】圖的中心集C（G）和邊緣集P（G）分別是指具有最小離心率的頂點組成的集合和最大離心率的頂點組成的集合.若圖G只有一個中心點，其他都是邊緣點，則稱圖G為幾乎邊緣圖（簡稱AP圖），半徑為r的AP圖稱為r-AP圖.本文主要是對文獻[1]中提出的問題給出結(jié)論及構(gòu)造的方法，給出半徑為3的AP圖的指標上界.若T是AP圖時，則T與K1，n-1同構(gòu)，最后證明了既是ASC圖又是AP圖的圖是P3.

【關鍵詞】中心集；邊緣集；AP圖；ASC圖；同構(gòu)

本文中考慮的圖都是連通圖.在圖G中，V（G）、E（G）分別表示其頂點集和邊集.頂點數(shù)又稱為圖的階.當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中添加最少的頂點構(gòu)造r-AP圖，則G是r-AP圖的誘導子圖，我們把添加的頂點數(shù)，稱為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對任意的整數(shù)r≥4，存在一個階為4r的r-AP圖.

證明若r≥4，則令Gr的構(gòu)造如下所述.它的頂點集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，對任意的整數(shù)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.