發(fā)布時間：2021-04-15 08:03

　　設(shè)T為具有n個頂點(diǎn)的樹圖,樹圖T的外圍維納指標(biāo)為T中所有外圍頂點(diǎn)對之間的距離之和,即PW （T）=■d （u, v）,其中P（T）為樹圖的所有外圍頂點(diǎn)構(gòu)成的集合.本文分別給出了具有完美匹配的樹圖的外圍維納指標(biāo)的上界和下界,以及外圍頂點(diǎn)數(shù)給定的具有完美匹配的樹圖的外圍維納指標(biāo)的上界和下界. 

【文章來源】：閩南師范大學(xué)學(xué)報(bào)(自然科學(xué)版). 2020,33(03)

【文章頁數(shù)】：6 頁

【部分圖文】：

引理2證明的示意圖Fig.1AgraphinLemma2wd（v）-1

v1v2v3v4v5圖4T3的示意圖Fig.4T3diagram第3期雷思宇：具有完美匹配樹圖的外圍維納指標(biāo)的上（下）界2.2完美匹配樹圖的外圍維納指標(biāo)的上（下）界文獻(xiàn)[3]證明了樹圖的外圍維納指標(biāo)的上（下）界，下面先給出具有完美匹配的樹圖的外圍維納指標(biāo)的下界.定理4若G∈T(2m,m)，m≥2，則1)若m≥2時，PW(G)≥3，等號成立當(dāng)且僅當(dāng)GP3；2)若m≥3時，PW(G)≥4，等號成立當(dāng)且僅當(dāng)GT3.證明1）因?yàn)閙≥2，所以至少有兩條邊，即d(G)≥2.若d(G)=2，則GSn，由引理2可得，任意懸掛點(diǎn)的關(guān)聯(lián)頂點(diǎn)的度應(yīng)為2，故此時Sn=P2，但是顯然P2不具有完美匹配，故矛盾，所以d(G)≥3.根據(jù)引理3，有PW(G)≥d(G)≥3.下面討論等號成立的情況.PW(G)=3時，一定有d(G)=3，因?yàn)槿鬱(G)≥4，則由引理3知PW(G)≥d(G)≥4，矛盾；若d(G)=2，則GSn，而由引理1可知PW(Sn)=(n-1)(n-2)，這時不存在頂點(diǎn)數(shù)n使得Sn的外圍維納指標(biāo)為3，矛盾.因?yàn)閐(G)=3，根據(jù)引理2直徑路徑兩側(cè)的懸掛點(diǎn)所關(guān)聯(lián)的頂點(diǎn)的度應(yīng)為2，所以此時有GP3，其匹配數(shù)m=2.即等號成立當(dāng)且僅當(dāng)GP3.得證.2）圖T3見圖4.因?yàn)閙≥3，則d(G)≥2.若d(G)=2，同1）中的證明可知，矛盾，故d(G)≥3.若d(G)=3，由1）中等號成立條件證明可知，GP3,m=2，矛盾.故d(G)≥4，所以由引理3有PW(G)≥d(G)≥4.下面討論等號成立的情況.

，不存在頂點(diǎn)數(shù)n使得Sn的外圍維納指標(biāo)為4，矛盾.因?yàn)閐(G)=4，所以會存在一條直徑，其頂點(diǎn)從左往右編號分別為v1v2v3v4v5，根據(jù)引理2，頂點(diǎn)v2,v4其度一定為2，若存在完美匹配，懸掛邊會在完美匹配中，則還有頂點(diǎn)v3沒被匹配，此時若在頂點(diǎn)v3上添加長度大于或等于2的路徑，則P(||G)≥3，有PW(G)>4，故頂點(diǎn)v3上只能添加1條懸掛邊，此時匹配數(shù)m=3.即等號成立當(dāng)且僅當(dāng)GT3.得證.2m-2kk—2k—2圖3T2的示意圖Fig.3T2diagram圖2T1的示意圖Fig.2T1diagramk-135


本文編號：3138953