關(guān)于幾乎邊緣圖的研究

劉海瓊

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

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

本文中考慮的圖都是連通圖.在圖G中，V（G）、E（G）分別表示其頂點(diǎn)集和邊集.頂點(diǎn)數(shù)又稱為圖的階.當(dāng)vi，vj∈V（G），vi和vj之間的距離是指在G中連接它們的最短路的長(zhǎng)度，用dG（vi，vj）表示.對(duì)任意的頂點(diǎn)vi∈V（G），vi的離心率是指在G中vi到其他頂點(diǎn)的最大距離，用εG（vi）表示.G的直徑用d（G）表示，它是指G中所有頂點(diǎn)的最大離心率.而G中所有頂點(diǎn)的最小離心率我們稱為半徑，用r（G）表示.若dG（u，v）=εG（v），則稱v是u的離心頂點(diǎn).當(dāng)εG（vi）=r（G）時(shí)，稱vi為G的中心頂點(diǎn)，類似的，若εG（vj）=d（G），則稱vj為G的直徑頂點(diǎn).若u∈V（G），則GuH是指圖H中每個(gè)點(diǎn)都和u相連.GH表示圖H中的每一個(gè)頂點(diǎn)都和圖G中的每一個(gè)點(diǎn)相連.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是幾乎自中心圖，簡(jiǎn)稱ASC圖.若|P（G）|=|V（G）|-1，則圖G是幾乎邊緣圖，簡(jiǎn)稱AP圖.半徑為r的ASC和AP圖稱為r-ASC和r-AP圖.在G中添加最少的頂點(diǎn)構(gòu)造r-AP圖，則G是r-AP圖的誘導(dǎo)子圖，我們把添加的頂點(diǎn)數(shù)，稱為r-ASC圖和r-AP圖的指標(biāo)，分別用θ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圖的問(wèn)題？下面給出肯定的回答：

定理1對(duì)任意的整數(shù)r≥4，存在一個(gè)階為4r的r-AP圖.

證明若r≥4，則令Gr的構(gòu)造如下所述.它的頂點(diǎn)集V（G）={u1，…，u2r+3}∪{v1，…，v2r-3}.

頂點(diǎn)u1，…，u2r+3誘導(dǎo)一個(gè)長(zhǎng)度為2r+3的圈，頂點(diǎn)u2，…u5，v2r-3，…，v1誘導(dǎo)另一個(gè)長(zhǎng)度為2r+1的圈，并且頂點(diǎn)vr-1連接ur+5.如圖所示.

下面我們證明G是r-AP圖.首先注意到vr-1既在圈長(zhǎng)為2r的圈中，又在圈長(zhǎng)為2r+1的圈中，所以eG（vr-1）=r.事實(shí)上由于頂點(diǎn)u1，…，u2r+3誘導(dǎo)的一個(gè)圈的長(zhǎng)度為2r+3所以我們立刻可以得出頂點(diǎn)u1，…，u2r+3的離心率都是r+1.若1≤i≤r-3，則對(duì)任意的頂點(diǎn)vi，有dG（vi，ur-i+4）=dG（vi，ur-i+3）=r+1，從而eG（vi）=r+1，當(dāng)i=r-2時(shí)，dG（vi，ur-i+4）=r+1即eG（vi）=r+1.由圖的對(duì)稱性可得，對(duì)于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是至少有兩個(gè)點(diǎn)的任意圖，則Φ2（G）≤5，等號(hào)成立當(dāng)且僅當(dāng)圖G是完全圖.

定理3若圖G是包含K3作為其誘導(dǎo)子圖的任意圖，則Φ3（G）≤9.

定理4如果圖G是一個(gè)r-AP圖，r≥1，u是圖G的中心頂點(diǎn)，則對(duì)任意的圖H，GuH是r-AP圖.

由定理4很容易得到下面兩個(gè)推論.

推論5若r≥2，則K1r-SC是1-AP圖.

推論6若圖G是半徑r≥2的圖，則K1G是1-AP圖.

引理7令圖的半徑為r，直徑為d，對(duì)任意的整數(shù)k，r≤k≤d，則至少存在兩個(gè)點(diǎn)的離心率為k.

定理8若樹T是AP圖，則T≌K1，n-1.

定理9若圖G既是ASC圖又是AP圖，則圖G是P3.

【參考文獻(xiàn)】

[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.