關(guān)于圖與線圖的距離指標(biāo)關(guān)系問(wèn)題研究

朱 娜盛興平

（1.安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001；2.阜陽(yáng)師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，安徽 阜陽(yáng) 236037）

0 引言

本文中所有的圖都是有限的,簡(jiǎn)單的,無(wú)向的.對(duì)于一個(gè)圖G，分別用V（G）和E（G）表示它的頂點(diǎn)集和邊集。G的一條途徑是指一個(gè)有限非空序列W＝v0e1v1e2v2…ekvk（0≤i≤k），它的項(xiàng)交替地為頂點(diǎn)和邊，ei的端點(diǎn)是vi-1和vi，稱W是從v0到vk的一條途徑，，v0和vk分別稱為W的起點(diǎn)和終點(diǎn)。若途徑W的邊e1，e2，…，ek互不相同，則W稱為跡。又若途徑W的頂點(diǎn)v0，v1，…vk也不相同，則W稱為路。路Pn=v0，v1，…vn表示頂點(diǎn)分別為v0，v1，…vn的路.如果跡的起點(diǎn)和終點(diǎn)相同，則稱為閉跡。若一條閉跡的起點(diǎn)和內(nèi)部頂點(diǎn)互不相同，則稱它為圈。[1]一個(gè)長(zhǎng)為n的圈記作Cn。如果V(H)U V(G)，E(H)U E(G)，并且ΦH是ΦG在E（H）上的限制，就稱H是G的子圖。假設(shè)V'是V的一個(gè)非空子集，以V'為頂點(diǎn)集，以兩端點(diǎn)均在V'中的邊的全體為邊集所組成的子圖，稱為G的由V'導(dǎo)出的子圖。

給定一個(gè)圖G，它的線圖L（G）滿足：V（L（G））＝E（ G），e1e2∈E（ L（ G）），當(dāng)且僅當(dāng)e1與e2在G中有公共點(diǎn)。對(duì)于v∈V（G），記dG（v）是v在G中的度，簡(jiǎn)記為d（v）。用δ（GV）表示G的頂點(diǎn)的最小度。對(duì)于v，u∈V（G），dG（u，v）（或者用d（u，v）） 表示在G中u和v之間最短路的長(zhǎng)度。對(duì)于e1e2∈E（G），定義dG（e1，e2）＝dL（G）（e1，e2）。W（G）指數(shù)是一個(gè)描述分子結(jié)構(gòu)的不變量，是化學(xué)圖論中最經(jīng)典的分子拓?fù)渲笖?shù)之一，它可以用于設(shè)計(jì)具有理想性質(zhì)的分子[2]。A.A.Dobrynin等人在2001年給出了樹(shù)的W（G）指數(shù)[3].A.A.Dobrynin等人在2002年給出了W（G）指數(shù)關(guān)于六角形系統(tǒng)的結(jié)果[4]。近些年，很多人對(duì)圖的W（G）指數(shù)和其線圖的W（L（G））指數(shù)的關(guān)系非常感興趣，尤其對(duì)于一個(gè)什么樣的圖滿足W（G）＝W（L（G））做了很多研究。Nathann Cohen等人在2009年給出了對(duì)于每一個(gè)非負(fù)整數(shù)g0存在g＞g0，當(dāng)圖G的圍長(zhǎng)為g時(shí)，有很多圖G滿足W（G）＝W（L（G））[5]。羅宇等人在2014年定義了一類具有圈數(shù)為r，圍長(zhǎng)為n的平面圖Gr，s，t，n并證明了對(duì)于滿足特定條件的正整數(shù)r，s，t，n，存在無(wú)窮個(gè)這樣的圖Gr，s，t，n滿足性質(zhì)W（ Gr，s，t，n）＝W（ L（Gr，s，t，n））[6]。關(guān)于W（ G ）指數(shù)的詳細(xì)內(nèi)容和結(jié)果參見(jiàn)[7-12]。本文中的S（G）是W（G）在定義上的簡(jiǎn)單推廣。記S（G）為圖G的所有頂點(diǎn)對(duì)之間的距離的平方和，即S（G）＝本文主要研究路，圈以及最小度數(shù)為2的圖G和其線圖的L（G）頂點(diǎn)對(duì)之間的距離的平方和的大小關(guān)系。

1 路和圈的結(jié)論

本部分首先研究路Pn和圈Cn與其對(duì)應(yīng)的線圖L（Pn）和L（Cn）的頂點(diǎn)對(duì)之間的距離平方和的大小關(guān)系。

定理1：對(duì)于任意一條路Pn，則有S（ L（Pn））

證明：用數(shù)學(xué)歸納法證明。對(duì)于n＝2，等式左邊等于S（ L（ Pn））＝ 0，等式右邊等于S（ Pn）－＝12-1＝0，左邊等于右邊，所以這個(gè)公式在n＝2時(shí)成立。

考慮完路的情況，下面我們?cè)倏紤]圈，由于對(duì)任意 Cn，Cn與L（Cn）同構(gòu)，故顯然有以下定理。

定理2：對(duì)于圈Cn，則有S（L（ Cn））＝S（Cn）。

對(duì)于雙圈圖的S（G）和S（L（G））的大小關(guān)系，沒(méi)有一般性的結(jié)論，下面舉例說(shuō)明.雙圈圖G1，G2，G3如圖1～圖3所示，有S（ G1）＝ 204，S（ L（ G1））＝ 173，S（ G2）＝ 60，S（ L（ G2））＝ 60，S（ G3）＝ 22，S（ L（ G3））＝ 35 則S（ G1）＞S（ L（ G1）），S（ G2）＝S（ L（ G2）），S（ G3）＜S（ L（ G3））。

由上面的例子可以看出雙圈圖中有S（G）＞S（L（G）），S（G）＝S（L（G））和S（G）＜S（L（G））。

圖1 G1

圖2 G2

圖3 G3

2 最小度至少為2的圖的結(jié)論

證明:假定d(v,v')=min{d(u,u')，d(u,v')，d(v,u')，d(v,v')}，可以得到

因此由(7)，(8)和(9)得到

定理3:G是連通圖且δ(G)≥ 2，S(G)＜S(L(G))，當(dāng)G是圈時(shí)等式成立.證明:如果G是圈，根據(jù)定理2等號(hào)成立.

因此，我們可以假定G至少有一個(gè)頂點(diǎn)的度至少3.通過(guò)引理2，我們有

令G2為G中二度頂點(diǎn)的導(dǎo)出子圖

由(13)和(14)得到