線圖、 全圖和細分圖的第一幾何-算數(shù)指數(shù)的上下界

霍英杰， 高玉斌

(中北大學 理學院， 山西 太原 030051)

0 引 言

拓撲指數(shù)通過分子結(jié)構(gòu)數(shù)值化產(chǎn)生， 是一種具有反映化合物結(jié)構(gòu)特征性質(zhì)的圖的不變量[1-2]. 近年來， 許多數(shù)學和化學工作者將研究重心放在研究特殊圖類的某種拓撲指數(shù)這一課題上. 2009年, Vukicevic.D等[3]提出了圖的第一幾何-算數(shù)指數(shù)(簡稱GA1指數(shù))的定義

(1)

式中：d(u),d(v)分別為頂點u和頂點v的度；E(G) 為G的邊集.

由于GA1指數(shù)是一種提出時間不久的拓撲指數(shù)， 所以目前的研究成果較少. Das. K C等[4-5]研究了連通圖GA1指數(shù)的一些上界和下界， 證明了界可達并刻畫了相應(yīng)極圖. 劉克強等[6]給出一定邊數(shù)的連通圖中線圖的GA1指標的上界或下界， 證明了這些界是可達的， 并刻畫了相應(yīng)的極圖. Mahmiani A.等[7]給出一定邊數(shù)及懸掛邊數(shù)的連通圖中全圖的GA1指標的界. 線圖、 全圖、 細分圖不僅是拓撲指數(shù)中重要的研究圖類[1,8-9]， 而且在化學等方面有著廣泛應(yīng)用[1,10].

本文通過對不等式進行放縮的方法， 將特定邊數(shù)的n階連通圖中線圖、 全圖的GA1指數(shù)的界推廣到n階連通圖中線圖、 全圖及細分圖的GA1指數(shù)的界， 得到了線圖、 全圖和細分圖的上下界， 且刻畫了達到上下界的極圖.

文中所考慮的圖G=(V(G),E(G))均為簡單圖， 其中V(G)是G的頂點集，E(G)是G的邊集，d(v)為點v在圖G中的度.

1 線圖的GA1指數(shù)

令EL={(u1v,vu2)|u1v,vu2∈E(G)}, 稱圖(E(G),EL)為圖G的線圖， 記為L(G).dL(v)表示點v在圖L(G)中的度.

由線圖的定義可知dL(u1v)=d(v)+d(u1)-2，dL(vu2)=d(v)+d(u2)-2， 其中v,u1,u2∈V(G)，u1v,vu2∈E(G).

定理 1 設(shè)G是n階連通圖， 最大度為Δ， 最小度為δ， 且δ≥2， 則

(2)

等式成立當且僅當d(v)=d(u)，G為正則圖.

證明 由式(1)知

(3)

由于δ≤d(v),d(u1),d(u2)≤Δ， 可得

即

且

又由于

故

(4)

等式成立當且僅當d(v)=d(u)， G為正則圖.

2 全圖的GA1指數(shù)

令ET={(v,uv)|uv∈E(G)}， 稱圖T(G)=(V(G)∪E(G),E(G)∪EL∪ET)為圖G的全圖， 記為T(G). dT(v)表示點v在圖T(G)中的度.

由全圖的定義知， dT(v)=2d(v)， dT(uv)=d(u)+d(v)， 其中u∈V(G), uv∈E(G).

定理 2 設(shè)G為n階連通圖， 邊數(shù)為m， 最大度為Δ， 最小度為δ， 且δ≥2， 則

(5)

等式成立當且僅當d(v)=d(u)， G為正則圖.

證明 令

由全圖的定義及式(1)知

GA1(T(G))=I1+I2+I3.

(6)

由于δ≤d(u)， d(v)≤Δ， 可得

即

且

又由于

故

綜合上式可得

(7)

等式成立當且僅當d(u)=d(v).

同樣， 仿照上面的證明方法， 還可以得到

(8)

(9)

故由式(6)～(9)可得到

等式成立當且僅當d(v)=d(u)，G為正則圖.

3 細分圖的GA1指數(shù)

將圖G中每條邊替換為P2(長為的路)后所得到的圖稱為G的細分圖， 記為S(G).

定理 3 設(shè)G是連通圖且邊數(shù)為m， 最大度Δ， 則

(10)

右側(cè)等式成立當且僅當G?Cn.

且

又由于

故

(11)

右邊等號成立當且僅當d(v)=d(u)=2， G?Cn.

定理 4 設(shè)G為n階連通圖， 最大度為Δ， 最小度為δ， 則

nΔ(Δ-1),

右邊等號成立當且僅當G?Cn.

證明 由定理3及線圖的定義可知

且

由于

(12)

故

nΔ(Δ-1),

右邊等號成立當且僅當G?Cn.

定理 5 設(shè)G是n階連通圖， 邊數(shù)為m， 最大度為Δ， 最小度為δ， 則

GA1(S(T(G)))≤6m+nΔ(Δ-1),

右邊等號成立當且僅當G?Cn.

證明 由定理3及全圖的定義可知

GA1(S(T(G)))≤2(|E(G)|+|EL|+|ET|),

|E(G)|+|EL|+|ET|=m+

由式(12)易知結(jié)論成立.

[1]GutmanI，EstradaE.Topologicalindicesbasedonthelinegraphofthemoleculargraph[J].JournalofChemicalInformationandComputerSciences， 1996， 36(3)： 541-543.

[2]TodeschiniR，ConsonniV.Handbookofmoleculardescriptors[M].Weinheim：Wiley-VCHVerlag， 2000.

[3]VukicevicD，F(xiàn)urturcaB.Topologicalindexbasedontherationsofgeometricalandarithmeticalmeansofend-vertexdegreesofedges[J].JournalofMathematicalChemistry， 2009， 46(4)： 1369-1376.

[4]DasKC.Ongeometric-arithmeticindexofgraphs[J].Match-CommunicationsinMathematicalandinComputerChemistry， 2010， 64(3)： 619-630.

[5]DasKC，GutmanI，F(xiàn)urtulaB.Onthefirstgeometric-arithmeticindexofgraph[J].DiscreteAppliedMathematics， 2011， 159(17)： 2030-2037.

[6]劉克強， 趙飚. 線圖的幾何-算數(shù)指標[J]. 江蘇師范大學學報(自然科學版)， 2014， 32(4)： 26-30.LiuKeqiang，ZhaoBiao.Ongeometric-arithmeticindexoflinegraph[J].JournalofJiangsuNormalUniversity(NaturalScienceEdition)， 2014， 32(4)： 26-30. (inChinese)

[7]MahmianiA，KhormaliO.Onthetotalversionofgeometric-arithmeticindex[J].MathematicalChemistry， 2013， 4(1)： 21-26.

[8]ChenZQ，MengJX，TianYZ.Onatom-bondconnectivityindexoflineandtotalgraphs[J].OperationsResearchTransactions， 2013， 17(3)： 1-10.

[9]孫曉玲， 高玉斌， 杜建偉. 線圖、 全圖和細分圖的augmentedZagreb指數(shù)[J]. 中北大學學報(自然科學版)， 2015， 36(1)： 1-4.SunXiaoling，GaoYubin，DuJianwei.AugmentedZagrebindexofline，totalandsubdivisiongraphs[J].JournalofNorthUniversityofChina(NaturalScienceEdition)， 2015， 36(1)： 1-4. (inChinese)

[10]GutmanI，Popovic，MishraBK，etal.Applicationoflinegraphsinphysicalchemistry[J].JournaloftheSerbianChemicalSociety， 1997， 62(11)： 1025-1029.